In questo articolo discuteremo dell'algoritmo di Prim. Insieme all'algoritmo vedremo anche la complessità, il funzionamento, l'esempio e l'implementazione dell'algoritmo di prim.
Prima di iniziare l'argomento principale, dovremmo discutere i termini fondamentali e importanti come spanning tree e spanning tree minimo.
Albero di copertura - Uno spanning tree è il sottografo di un grafo connesso non orientato.
Albero di copertura minimo - L'albero di copertura minimo può essere definito come l'albero di copertura in cui la somma dei pesi del bordo è minima. Il peso dello spanning tree è la somma dei pesi dati ai bordi dello spanning tree.
Ora iniziamo l'argomento principale.
Algoritmo di Prim è un algoritmo greedy utilizzato per trovare l'albero di copertura minimo da un grafico. L'algoritmo di Prim trova il sottoinsieme di archi che include ogni vertice del grafico in modo tale che la somma dei pesi degli archi possa essere minimizzata.
L'algoritmo di Prim inizia con il singolo nodo ed esplora ad ogni passo tutti i nodi adiacenti con tutti gli spigoli di connessione. Sono stati selezionati i bordi con i pesi minimi che non causano cicli nel grafico.
Come funziona l'algoritmo di Prim?
L'algoritmo di Prim è un algoritmo goloso che parte da un vertice e continua ad aggiungere gli archi con il peso minore fino al raggiungimento dell'obiettivo. I passaggi per implementare l'algoritmo di Prim sono i seguenti:
- Per prima cosa dobbiamo inizializzare un MST con il vertice scelto casualmente.
- Ora dobbiamo trovare tutti gli spigoli che collegano l'albero nel passaggio precedente con i nuovi vertici. Dai bordi trovati, seleziona il bordo minimo e aggiungilo all'albero.
- Ripetere il passaggio 2 finché non si forma l'albero ricoprente minimo.
Le applicazioni dell'algoritmo di Prim sono:
- L'algoritmo di Prim può essere utilizzato nella progettazione di reti.
- Può essere utilizzato per realizzare cicli di rete.
- Può essere utilizzato anche per stendere i cavi dei collegamenti elettrici.
Esempio dell'algoritmo di Prim
Ora vediamo il funzionamento dell'algoritmo di Prim utilizzando un esempio. Sarà più semplice comprendere l'algoritmo di Prim utilizzando un esempio.
Supponiamo che un grafico ponderato sia:
Passo 1 - Per prima cosa dobbiamo scegliere un vertice dal grafico sopra. Scegliamo B.
Java ottiene l'ora corrente
Passo 2 - Ora dobbiamo scegliere e aggiungere lo spigolo più corto dal vertice B. Ci sono due spigoli dal vertice B che vanno da B a C con peso 10 e dallo spigolo da B a D con peso 4. Tra gli spigoli, lo spigolo BD ha il peso minimo . Quindi, aggiungilo al MST.
Passaggio 3: Ora, ancora una volta, scegli il bordo con il peso minimo tra tutti gli altri bordi. In questo caso, gli archi DE e CD sono tali archi. Aggiungili a MST ed esplora l'adiacente di C, cioè E e A. Quindi, seleziona il bordo DE e aggiungilo a MST.
Passaggio 4: Ora seleziona il CD edge e aggiungilo a MST.
Passaggio 5: Ora scegli l'edge CA. Qui non possiamo selezionare il bordo CE poiché creerebbe un ciclo nel grafico. Quindi, scegli l'edge CA e aggiungilo al MST.
Pertanto, il grafico prodotto nel passaggio 5 è l'albero di copertura minimo del grafico dato. Il costo del MST è riportato di seguito:
Costo di MST = 4 + 2 + 1 + 3 = 10 unità.
Algoritmo
Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT
Complessità dell'algoritmo di Prim
Vediamo ora la complessità temporale dell'algoritmo di Prim. Il tempo di esecuzione dell'algoritmo di Prim dipende dall'utilizzo della struttura dati per il grafico e dall'ordinamento degli archi. La tabella seguente mostra alcune scelte:
| Struttura dati utilizzata per il peso minimo del bordo | Complessità temporale |
|---|---|
| Matrice di adiacenza, ricerca lineare | O(|V|2) |
| Lista di adiacenza e heap binario | O(|E| log |V|) |
| Lista di adiacenza e heap di Fibonacci | O(|E|+ |V| log |V|) |
L'algoritmo di Prim può essere semplicemente implementato utilizzando la matrice di adiacenza o la rappresentazione grafica della lista di adiacenza e per aggiungere il bordo con il peso minimo è necessaria la ricerca lineare di un array di pesi. Richiede O(|V|2) tempo di esecuzione. Può essere ulteriormente migliorato utilizzando l'implementazione dell'heap per trovare i bordi di peso minimo nel ciclo interno dell'algoritmo.
La complessità temporale dell'algoritmo di Prim è O(E logV) o O(V logV), dove E è il n. di bordi e V è il n. di vertici.
Implementazione dell'algoritmo di Prim
Vediamo ora l'implementazione dell'algoritmo di prim.
Programma: Scrivere un programma per implementare l'algoritmo di prim in linguaggio C.
#include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
weight
'); printf(' %d
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>