Kruskal vs Prim
In informatica, gli algoritmi di Prim e Kruskal sono un algoritmo avido che trova uno spanning tree minimo per un grafo connesso ponderato e non orientato. Uno spanning tree è un sottografo di un grafo tale che ogni nodo del grafo è collegato da un percorso, che è un albero. Ogni spanning tree ha un peso e il peso/costo minimo possibile di tutti gli spanning tree è il minimo spanning tree (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 arco, 1. Seleziona un nodo arbitrario dal grafico e aggiungilo all'albero T (che sarà il primo nodo)
2. Considera i pesi di ciascun arco connesso ai nodi nell'albero e seleziona il minimo. Aggiungi il bordo e il nodo all' altra estremità dell'albero T e rimuovi il bordo dal grafico. (Selezionare qualsiasi se esistono due o più minimi)
3. Ripetere il passaggio 2, finché non vengono aggiunti n-1 bordi 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 grafo deve essere un grafo connesso. La forma base dell'algoritmo di Prim ha una complessità temporale di O(V2).
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 il rispettivo peso di ciascun arco, 1. Seleziona l'arco con il minor peso dell'intero grafico e aggiungi all'albero ed elimina 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. (Selezionare qualsiasi se esistono due o più minimi)
3. Ripetere la procedura al punto 2.
In questo metodo, l'algoritmo inizia con il lato meno ponderato e continua a selezionare ciascun lato ad ogni ciclo. Pertanto, nell'algoritmo il grafo non deve essere connesso. 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 fronte.
• 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 connesso mentre quello di Kruskal può funzionare anche su grafici disconnessi.
• L'algoritmo di Prim ha una complessità temporale di O(V2), e la complessità temporale di Kruskal è O(logV).
