Algoritmo Spanning Tree di Prim

L'algoritmo di Prim per trovare l'albero di copertura del costo minimo (come l'algoritmo di Kruskal) utilizza l'approccio avido. L'algoritmo di Prim condivide una somiglianza con il fileshortest path first algoritmi.

L'algoritmo di Prim, in contrasto con l'algoritmo di Kruskal, tratta i nodi come un singolo albero e continua ad aggiungere nuovi nodi allo spanning tree dal grafo dato.

Per contrastare l'algoritmo di Kruskal e per comprendere meglio l'algoritmo di Prim, useremo lo stesso esempio:

Passaggio 1: rimuovere tutti gli anelli e i bordi paralleli

Rimuovi tutti i loop e i bordi paralleli dal grafico dato. In caso di bordi paralleli, mantenere quello a cui è associato il minor costo e rimuovere tutti gli altri.

Passaggio 2: scegliere un nodo arbitrario come nodo radice

In questo caso, scegliamo Snode come nodo radice dello spanning tree di Prim. Questo nodo viene scelto arbitrariamente, quindi qualsiasi nodo può essere il nodo radice. Ci si potrebbe chiedere perché qualsiasi video possa essere un nodo radice. Quindi la risposta è che nello spanning tree sono inclusi tutti i nodi di un grafo e poiché è connesso deve esserci almeno un bordo, che lo unirà al resto dell'albero.

Passaggio 3: controlla i bordi in uscita e seleziona quello con un costo inferiore

Dopo aver scelto il nodo radice S, vediamo che S, A e S, C sono due bordi con peso 7 e 8, rispettivamente. Scegliamo il bordo S, A in quanto è minore dell'altro.

Ora, l'albero S-7-A è trattato come un nodo e controlliamo che tutti i bordi escano da esso. Selezioniamo quello che ha il costo più basso e lo includiamo nell'albero.

Dopo questo passaggio, viene formato l'albero S-7-A-3-C. Ora lo tratteremo di nuovo come un nodo e controlleremo di nuovo tutti i bordi. Tuttavia, sceglieremo solo il vantaggio più economico. In questo caso, C-3-D è il nuovo bordo, che è inferiore al costo di altri bordi 8, 6, 4, ecc.

Dopo aver aggiunto node Dallo spanning tree, ora abbiamo due archi che ne escono aventi lo stesso costo, cioè D-2-T e D-2-B. Quindi, possiamo aggiungere uno dei due. Ma il passaggio successivo restituirà nuovamente il bordo 2 come il costo minimo. Quindi, stiamo mostrando uno spanning tree con entrambi i bordi inclusi.

Potremmo scoprire che l'output spanning tree dello stesso grafico utilizzando due algoritmi diversi è lo stesso.