Differenza tra Kruskal e Prim

Kruskal vs Prim

Nell'informatica, gli algoritmi di Prim e Kruskal sono un algoritmo avido che trova uno spanning tree minimo per un grafo orientato ponderato connesso. Uno spanning tree è un sottografo di un grafico tale che ogni nodo del grafo è connesso da un percorso, che è un albero. Ogni albero spanning ha un peso e il minimo peso / costo possibile di tutti gli alberi spanning è l'albero di copertura 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 grafico 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. Considerare i pesi di ciascun lato connesso ai nodi nell'albero e selezionare 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 almeno due o più)

3. Ripetere il passaggio 2, finché i bordi n-1 non 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 collegato. La forma base dell'algoritmo di Prim ha una complessità temporale di O (V²).

Maggiori 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 bordo,

1. Seleziona l'arco con il peso minimo dell'intero grafico e aggiungi all'albero ed elimina dal grafico.

2. Del rimanente selezionare il bordo meno ponderato, in modo da non formare un ciclo. Aggiungi il bordo all'albero ed elimina dal grafico. (Seleziona uno qualsiasi se esistono almeno due o più)

3. Ripetere la procedura al punto 2.

In questo metodo, l'algoritmo inizia con il bordo meno ponderato e continua selezionando ogni spigolo 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 Kruskal e Prim's Algorithm?

• 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 passo.

• Nell'algoritmo di prim, il grafico deve essere un grafico collegato mentre il Kruskal può funzionare anche su grafici scollegati.

• L'algoritmo di Prim ha una complessità temporale di O (V²), e la complessità temporale di Kruskal è O (logV).