2.5 Algoritmo di Kruskal

Parte 2 · Alberi e cammini · Capitolo 2 · Capitolo 2: Alberi ricoprenti · Dispensa, volume 2 (PDF) · Esercizi: Alberi ricoprenti · App: Alberi ricoprenti minimi: Kruskal e Prim

Algoritmo: Algoritmo di Kruskal

Input: un grafo connesso non orientato \(G=(V,E)\) con pesi \(w_e\)

Output: un albero di copertura minimo \(F\)

1Passaggio 0 (inizializzazione). Ordina i lati in base al peso non decrescente, \(w_{e_1} \le w_{e_2} \le \dots \le w_{e_m}\), and set \(F:=\emptyset\).

2Passaggio 1 (scansione). Per \(k=1,2,\dots,m\): se i punti finali di \(e_k\) si trovano in componenti diversi di \((V,F)\), impostare \(F:=F \cup \{e_k\}\); altrimenti rifiuta \(e_k\).

3 Se \(|F|=n-1\), STOP.

• Un lato è accettato se unisce due diversi componenti di \((V,F)\) e rifiutato se lo farebbe chiudere un ciclo. I componenti di \((V,F)\) iniziano come singoli vertici \(n\) e si fondono ad ogni accettazione.

• In questo modulo, i lati di uguale peso vengono scansionati in ordine lessicografo di \(\{u,v\}\), con \(u<v\).

Teorema 2.10: correttezza dell'algoritmo di Kruskal

L'algoritmo di Kruskal si ferma con \(|F|=n-1\) e \(F\) è uno albero ricoprente minimo.

Dimostrazione

Mostriamo che ogni lato accettato \(e_k=\{u,v\}\) è una scelta del passo 2 dell'algoritmo greedy generico. Lasciamo \(S\) è il componente di \((V,F)\) che contiene \(u\), subito prima che \(e_k\) venga accettato: \(v \notin S\) e nessun lato di \(F\) incrocia \(\delta(S)\).

1. Lascia che \(e_h \in \delta(S)\) con \(h<k\). Quando \(e_h\) è stato scansionato non è stato accettato, poiché \(F \cap \delta(S)=\emptyset\); quindi è allora gli estremo erano nello stesso componente e lo sono ancora, perché i componenti si uniscono solo. Ciò contraddice \(e_h \in \delta(S)\).

2. Quindi ogni lato di \(\delta(S)\) è un certo \(e_h\) con \(h \ge k\) e \(w_{e_h} \ge w_{e_k}\): \(e_k\) ha un minimo peso in \(\delta(S)\).

3. Se la scansione terminasse con \(|F|<n-1\), la foresta \((V,F)\) avrebbe due componenti uniti da un lato di \(G\) e quel lato sarebbe stato accettato una volta scansionato, secondo l'argomentazione del punto 1.

Secondo Teorema 2.9, \(F\) è uno albero ricoprente minimo. □

2.5.1 Implementazione e tempo di esecuzione

• I componenti di \((V,F)\) sono mantenuti in una struttura union–find: ogni vertice \(v\) memorizza l'etichetta \(\mathit{comp}(v)\) del suo componente e ogni componente memorizza l'elenco dei suoi vertici e la sua dimensione.

• Testare se \(u\) e \(v\) si trovano in componenti diversi è il confronto \(\mathit{comp}(u) \neq \mathit{comp}(v)\), in \(O(1)\) tempo. L'unione di due componenti rietichetta i vertici di più piccolo (unione per dimensione).

Teorema 2.11: tempo di esecuzione dell'algoritmo di Kruskal

Con la struttura unione-trova per etichette e unione per dimensione, l'algoritmo di Kruskal viene eseguito nel tempo \(O(m\log n)\).

Dimostrazione

1. L'ordinamento dei lati richiede tempo \(O(m\log m)\); da \(m \le n^2\), \(\log m \le 2\log n\) e questo è \(O(m\log n)\).

2. La scansione esegue i test \(m\), ciascuno nel tempo \(O(1)\).

3. Quando un vertice cambia rappresentante, il suo componente si fonde con un componente di dimensione almeno pari. La dimensione del componente almeno raddoppia e non supera mai \(n\); quindi ogni vertice cambia rappresentante al massimo \(\log_2 n\) volte. Tutte le fusioni richiedono complessivamente tempo \(O(n\log n)\).

\(G\) è connesso, quindi \(n-1 \le m\) e il totale è \(O(m\log n+n\log n)=O(m\log n)\). □

• Il tempo di esecuzione è dominato dall'ordinamento. Con l'unione: trova la struttura per alberi, con l'unione per rango e compressione del percorso, la scansione richiede un tempo quasi lineare; il limite rimane \(O(m\log n)\) a causa dell'ordinamento.

• L'algoritmo utilizza solo confronti tra pesi: ogni trasformazione crescente dei pesi dà il stesso albero.

2.5.2 Algoritmo di Kruskal sul grafo di riferimento

Esempio 2.7: Algoritmo di Kruskal

Eseguiamo l'algoritmo di Kruskal sul grafo di riferimento ponderato. I lati in ordine di peso sono \(\{1,3\},\{4,5\},\{2,3\},\{1,2\},\{3,4\},\{2,4\},\{5,6\},\{3,5\},\{4,6\}\). Ogni riga rappresenta un lato scansionato, con il componenti di \((V,F)\) dopo il passaggio:

\(k\)	lato \(e_k\)	\(w_{e_k}\)	decisione e componenti di \((V,F)\)
\(1\)	\(\{1,3\}\)	\(1\)	accetta: \(\{1,3\},\{2\},\{4\},\{5\},\{6\}\)
\(2\)	\(\{4,5\}\)	\(2\)	accetta: \(\{1,3\},\{2\},\{4,5\},\{6\}\)
\(3\)	\(\{2,3\}\)	\(3\)	accetta: \(\{1,2,3\},\{4,5\},\{6\}\)
\(4\)	\(\{1,2\}\)	\(4\)	rifiuta (\(1\) e \(2\) sono entrambi in \(\{1,2,3\}\))
\(5\)	\(\{3,4\}\)	\(5\)	accetta: \(\{1,2,3,4,5\},\{6\}\)
\(6\)	\(\{2,4\}\)	\(6\)	rifiuta (\(2\) e \(4\) sono entrambi in \(\{1,2,3,4,5\}\))
\(7\) e \(\{5,6\}\) e \(7\) e accetta: \(\{1,2,3,4,5,6\}\); \(|F|=5\), STOP

L'algoritmo si ferma dopo \(7\) dei lati \(9\), con \(F=\{\{1,3\},\{4,5\},\{2,3\},\{3,4\},\{5,6\}\}\) di peso \(18\): l'albero \(\tilde{F}\) di Esempio 2.2. La figura mostra, su ciascun lato dell'albero, il suo peso e il peso tra parentesi il passo \(k\) della sua accettazione.

• I lati scartati \(\{1,2\}\) e \(\{2,4\}\) sono i lati più pesanti dei cicli \(1,2,3\) e \(2,3,4\), poiché la proprietà del ciclo prevede; i lati \(\{3,5\}\) e \(\{4,6\}\) non vengono mai scansionati.

L'algoritmo di Kruskal scansiona gli lati con peso non decrescente e accetta quelli che uniscono due componenti; con union: trova che viene eseguito nel tempo \(O(m\log n)\), dominato dall'ordinamento.

---

Avanti: 2.6 Algoritmo di Prim