Kruskal contro Prim
In informatica, gli algoritmi di Prim e Kruskal sono un algoritmo avido che trova uno spanning tree minimo per un grafo non orientato pesato connesso. Uno spanning tree è un sottografo di un grafo tale che ogni nodo del grafo è connesso da un percorso, che è un albero. Ogni spanning tree ha un peso e il peso / costo minimo possibile di tutti gli spanning tree è lo spanning tree minimo (MST).
Ulteriori informazioni sull'algoritmo di Prim
L'algoritmo è stato sviluppato dal matematico ceco Vojtěch Jarník nel 1930 e successivamente in modo indipendente dallo scienziato informatico Robert C. Prim nel 1957. È stato riscoperto da Edsger Dijkstra nel 1959. L'algoritmo può essere definito in tre passaggi chiave;
Dato il grafo connesso con n nodi e il rispettivo peso di ciascun bordo, 1. Seleziona un nodo arbitrario dal grafico e aggiungilo all'albero T (che sarà il primo nodo)
2. Considera i pesi di ciascun bordo connesso ai nodi dell'albero e seleziona il minimo. Aggiungi il bordo e il nodo all'altra estremità dell'albero T e rimuovi il bordo dal grafico. (Seleziona uno qualsiasi se esistono due o più minimi)
3. Ripetere il passaggio 2, fino a quando n-1 bordi vengono aggiunti all'albero.
In questo metodo, l'albero inizia con un singolo nodo arbitrario e si espande da quel nodo in poi ad ogni ciclo. Quindi, affinché l'algoritmo funzioni correttamente, il grafico deve essere un grafico connesso. La forma base dell'algoritmo di Prim ha una complessità temporale di O (V 2).
Ulteriori informazioni sull'algoritmo di Kruskal
L'algoritmo sviluppato da Joseph Kruskal è apparso negli atti dell'American Mathematical Society nel 1956. L'algoritmo di Kruskal può anche essere espresso in tre semplici passaggi.
Dato il grafico con n nodi e rispettivo peso di ciascun bordo, 1. Selezionare l'arco con il peso minore dell'intero grafico e aggiungerlo all'albero ed eliminarlo dal grafico.
2. Dei restanti selezionare il bordo meno pesato, in modo da non formare un ciclo. Aggiungi il bordo all'albero ed elimina dal grafico. (Seleziona uno qualsiasi se esistono due o più minimi)
3. Ripetere la procedura nel passaggio 2.
In questo metodo, l'algoritmo inizia con il bordo meno pesato e continua a selezionare ciascun bordo ad ogni ciclo. Pertanto, nell'algoritmo non è necessario collegare il grafico. L'algoritmo di Kruskal ha una complessità temporale di O (logV)
Qual è la differenza tra l'algoritmo di Kruskal e quello di Prim?
• L'algoritmo di Prim si inizializza con un nodo, mentre l'algoritmo di Kruskal inizia con un bordo.
• Gli algoritmi di Prim si estendono da un nodo all'altro mentre l'algoritmo di Kruskal seleziona i bordi in modo che la posizione del bordo non sia basata sull'ultimo passaggio.
• Nell'algoritmo di prim, il grafico deve essere un grafo connesso mentre quello di Kruskal può funzionare anche su grafi scollegati.
• L'algoritmo di Prim ha una complessità temporale di O (V 2) e la complessità temporale di Kruskal è O (logV).
