Differenza tra Kruskal e Prim: Kruskal vs Prim

Kruskal vs Prim

Nella scienza dell'informazione, gli algoritmi di Prim e di Kruskal sono un algoritmo avido che trova un albero minimo spanning per un grafico non collegato ponderato collegato. Un albero spanning è un sottogramma di un grafico tale che ogni nodo del grafico è collegato da un percorso, che è un albero. Ogni albero spanning ha un peso, e il minimo possibile pesi / costo di tutti gli alberi spanning è l'albero minimo spanning (MST).

L'algoritmo è stato sviluppato dal matematico ceco Vojtěch Jarník nel 1930 e successivamente in modo indipendente dal computer scientista Robert C. Prim nel 1957. È stato riscoperto da Edsger Dijkstra nel 1959. l'algoritmo può essere dichiarato in tre passaggi chiave;

Dato il grafico connesso con n nodi e rispettivo peso di ogni bordo,

1. Selezionare un nodo arbitrario dal grafico e aggiungerlo all'albero T (che sarà il primo nodo)

2. Considerate i pesi di ogni bordo collegati ai nodi dell'albero e selezionate il minimo. Aggiungere il bordo e il nodo all'altra estremità dell'albero T e rimuovere il bordo dal grafico. (Selezionare se esistono due o più minimi)

3. Ripetere il passaggio 2, finché i n-1 bordi non vengono aggiunti all'albero.

In questo metodo, l'albero inizia con un singolo nodo arbitrario e si espande da quel nodo in avanti con ciascun ciclo. Quindi, affinché l'algoritmo funzioni correttamente, il grafico deve essere un grafo collegato. La forma di base dell'algoritmo di Prim ha una complessità temporale di O (V

2).

Più di Algoritmo di Kruskal ^{L'algoritmo sviluppato da Joseph Kruskal è apparso negli atti della American Mathematical Society nel 1956. L'algoritmo di Kruskal può anche essere espresso in tre semplici passi.} Considerato il grafico con i n nodi e il rispettivo peso di ogni bordo,

1. Selezionare l'arco con il peso minore dell'intero grafico e aggiungere all'albero e cancellarlo dal grafico.

2. Delle restanti selezionate il bordo meno pesato, in modo che non formi un ciclo. Aggiungere il bordo all'albero ed eliminarlo dal grafico. (Selezionare se esistono due o più minimi)

3. Ripetere il processo nel passaggio 2.

In questo metodo, l'algoritmo inizia con il bordo meno pesato e continua a selezionare ogni bordo ad ogni ciclo. Pertanto, nell'algoritmo il grafico non deve essere collegato. L'algoritmo di Kruskal ha una complessità temporale di O (logV)

Qual è la differenza tra l'algoritmo di Kruskal e di Prim?

• L'algoritmo di Prim viene inizializzato con un nodo, mentre l'algoritmo di Kruskal inizia con un bordo.

• Gli algoritmi di Prim si spanano 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.

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

• L'algoritmo di Prim ha una complessità temporale di O (V

2), e la complessità temporale di Kruskal è O (logV).