Introduzione all’algoritmo di Prim:
Noi abbiamo discusso Algoritmo di Kruskal per il Minimum Spanning Tree . Come l’algoritmo di Kruskal, anche l’algoritmo di Prim è a Algoritmo goloso . Questo algoritmo inizia sempre con un singolo nodo e si sposta attraverso diversi nodi adiacenti, per esplorare tutti i bordi collegati lungo il percorso.
L'algoritmo inizia con uno spanning tree vuoto. L'idea è di mantenere due serie di vertici. Il primo insieme contiene i vertici già inclusi nel MST, mentre l'altro insieme contiene i vertici non ancora inclusi. Ad ogni passo, considera tutti i bordi che collegano i due insiemi e sceglie il bordo di peso minimo da questi bordi. Dopo aver selezionato il bordo, sposta l'altro punto finale del bordo nel set contenente MST.
Viene chiamato un gruppo di archi che collega due insiemi di vertici in un grafico taglio nella teoria dei grafi . Quindi, ad ogni passo dell'algoritmo di Prim, trova un taglio, scegli il bordo di peso minimo dal taglio e includi questo vertice in MST Set (l'insieme che contiene i vertici già inclusi).
Come funziona l'algoritmo di Prim?
Il funzionamento dell’algoritmo di Prim può essere descritto utilizzando i seguenti passaggi:
Passo 1: Determina un vertice arbitrario come vertice iniziale del MST.
Passo 2: Segui i passaggi da 3 a 5 finché non ci sono vertici che non sono inclusi nell'MST (noti come vertici marginali).
Passaggio 3: Trova i bordi che collegano qualsiasi vertice dell'albero con i vertici delle frange.
Passaggio 4: Trova il minimo tra questi bordi.
Passaggio 5: Aggiungere il bordo scelto al MST se non forma alcun ciclo.
Passaggio 6: Restituisci il MST ed esci
Nota: Per determinare un ciclo, possiamo dividere i vertici in due insiemi [un insieme contiene i vertici inclusi in MST e l'altro contiene i vertici marginali.]
Pratica consigliata Albero di copertura minimo Provalo!Illustrazione dell'algoritmo di Prim:
Consideriamo il grafico seguente come un esempio per il quale dobbiamo trovare il Minimum Spanning Tree (MST).
Esempio di un grafico
Passo 1: Innanzitutto, selezioniamo un vertice arbitrario che funge da vertice iniziale del Minimum Spanning Tree. Qui abbiamo selezionato il vertice 0 come vertice iniziale.
0 è selezionato come vertice iniziale
Passo 2: Tutti gli spigoli che collegano l'MST incompleto e gli altri vertici sono gli spigoli {0, 1} e {0, 7}. Tra questi due il bordo con peso minimo è {0, 1}. Quindi includi il bordo e il vertice 1 nel MST.
1 viene aggiunto al MST
Passaggio 3: Gli archi che collegano l'MST incompleto ad altri vertici sono {0, 7}, {1, 7} e {1, 2}. Tra questi bordi il peso minimo è 8 che è dei bordi {0, 7} e {1, 2}. Includiamo qui lo spigolo {0, 7} e il vertice 7 nel MST. [Avremmo potuto includere anche il bordo {1, 2} e il vertice 2 nel MST].
7 è aggiunto nel MST
Passaggio 4: Gli archi che collegano l'MST incompleto con i vertici delle frange sono {1, 2}, {7, 6} e {7, 8}. Aggiungi il bordo {7, 6} e il vertice 6 nel MST poiché ha il peso minore (cioè 1).
6 è aggiunto nel MST
Passaggio 5: Gli archi di connessione ora sono {7, 8}, {1, 2}, {6, 8} e {6, 5}. Includere il bordo {6, 5} e il vertice 5 nel MST poiché il bordo ha il peso minimo (cioè 2) tra di loro.
Includere il vertice 5 nel MST
Passaggio 6: Tra gli archi di connessione attuali, l'arco {5, 2} ha il peso minimo. Quindi includi quel bordo e il vertice 2 nel MST.
Includere il vertice 2 nel MST
Passaggio 7: Gli archi di connessione tra l'MST incompleto e gli altri archi sono {2, 8}, {2, 3}, {5, 3} e {5, 4}. Il bordo con peso minimo è il bordo {2, 8} che ha peso 2. Quindi includi questo bordo e il vertice 8 nel MST.
Aggiungi il vertice 8 nel MST
Passaggio 8: Vedi qui che i bordi {7, 8} e {2, 3} hanno entrambi lo stesso peso che è minimo. Ma 7 fa già parte del MST. Quindi considereremo il bordo {2, 3} e includeremo quel bordo e il vertice 3 nel MST.
Includere il vertice 3 in MST
Passaggio 9: Resta da includere solo il vertice 4. Il margine pesato minimo dall'MST incompleto a 4 è {3, 4}.
Includere il vertice 4 nel MST
La struttura finale del MST è la seguente e il peso dei bordi del MST è (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
La struttura dell'MST formata utilizzando il metodo sopra
Nota: Se avessimo selezionato il bordo {1, 2} nel terzo passaggio, l'MST sarebbe simile al seguente.
Struttura dell'MST alternativo se avessimo selezionato il bordo {1, 2} nell'MST
Come implementare l'algoritmo di Prim?
Seguire i passaggi indicati per utilizzare il Algoritmo di Prim menzionato sopra per trovare MST di un grafico:
- Crea un set mstSet che tiene traccia dei vertici già inclusi in MST.
- Assegnare un valore chiave a tutti i vertici nel grafico di input. Inizializza tutti i valori chiave come INFINITE. Assegnare il valore chiave come 0 per il primo vertice in modo che venga selezionato per primo.
- Mentre mstSet non include tutti i vertici
- Scegli un vertice In quello non c'è mstSet e ha un valore chiave minimo.
- Includere In nel mstSet .
- Aggiorna il valore chiave di tutti i vertici adiacenti di In . Per aggiornare i valori chiave, scorrere tutti i vertici adiacenti.
- Per ogni vertice adiacente In , se il peso del bordo u-v è inferiore al valore chiave precedente di In , aggiorna il valore chiave come peso di u-v .
L'idea di utilizzare i valori chiave è quella di scegliere il limite di peso minimo dal taglio . I valori chiave vengono utilizzati solo per i vertici che non sono ancora inclusi in MST, il valore chiave per questi vertici indica i bordi di peso minimo che li collegano all'insieme di vertici inclusi in MST.
Di seguito è riportata l’implementazione dell’approccio:
C++
// A C++ program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> using> namespace> std;> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout << 'Edge Weight
'; for (int i = 1; i cout << parent[i] << ' - ' << i << ' ' << graph[i][parent[i]] << '
'; } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // Print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; } // This code is contributed by rathbhupendra> |
prepararsi per il test mockito
>
>
C
// A C program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> #include> #include> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] int printMST(int parent[], int graph[V][V]) { printf('Edge Weight
'); for (int i = 1; i printf('%d - %d %d
', parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; }> |
>
>
Giava
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> >// Number of vertices in the graph> >private> static> final> int> V =>5>;> >// A utility function to find the vertex with minimum> >// key value, from the set of vertices not yet included> >// in MST> >int> minKey(>int> key[], Boolean mstSet[])> >{> >// Initialize min value> >int> min = Integer.MAX_VALUE, min_index = ->1>;> >for> (>int> v =>0>; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
>
>
Python3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> [[>0> for> column>in> range>(vertices)]> >for> row>in> range>(vertices)]> ># A utility function to print> ># the constructed MST stored in parent[]> >def> printMST(>self>, parent):> >print>(>'Edge Weight'>)> >for> i>in> range>(>1>,>self>.V):> >print>(parent[i],>'-'>, i,>' '>,>self>.graph[i][parent[i]])> ># A utility function to find the vertex with> ># minimum distance value, from the set of vertices> ># not yet included in shortest path tree> >def> minKey(>self>, key, mstSet):> ># Initialize min value> >min> => sys.maxsize> >for> v>in> range>(>self>.V):> >if> key[v] <>min> and> mstSet[v]>=>=> False>:> >min> => key[v]> >min_index>=> v> >return> min_index> ># Function to construct and print MST for a graph> ># represented using adjacency matrix representation> >def> primMST(>self>):> ># Key values used to pick minimum weight edge in cut> >key>=> [sys.maxsize]>*> self>.V> >parent>=> [>None>]>*> self>.V># Array to store constructed MST> ># Make key 0 so that this vertex is picked as first vertex> >key[>0>]>=> 0> >mstSet>=> [>False>]>*> self>.V> >parent[>0>]>=> ->1> # First node is always the root of> >for> cout>in> range>(>self>.V):> ># Pick the minimum distance vertex from> ># the set of vertices not yet processed.> ># u is always equal to src in first iteration> >u>=> self>.minKey(key, mstSet)> ># Put the minimum distance vertex in> ># the shortest path tree> >mstSet[u]>=> True> ># Update dist value of the adjacent vertices> ># of the picked vertex only if the current> ># distance is greater than new distance and> ># the vertex in not in the shortest path tree> >for> v>in> range>(>self>.V):> ># graph[u][v] is non zero only for adjacent vertices of m> ># mstSet[v] is false for vertices not yet included in MST> ># Update the key only if graph[u][v] is smaller than key[v]> >if> self>.graph[u][v]>>0> and> mstSet[v]>=>=> False> > >and> key[v]>>self>.graph[u][v]:> >key[v]>=> self>.graph[u][v]> >parent[v]>=> u> >self>.printMST(parent)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph(>5>)> >g.graph>=> [[>0>,>2>,>0>,>6>,>0>],> >[>2>,>0>,>3>,>8>,>5>],> >[>0>,>3>,>0>,>0>,>7>],> >[>6>,>8>,>0>,>0>,>9>],> >[>0>,>5>,>7>,>9>,>0>]]> >g.primMST()> # Contributed by Divyanshu Mehta> |
>
>
C#
// A C# program for Prim's Minimum> // Spanning Tree (MST) algorithm.> // The program is for adjacency> // matrix representation of the graph> using> System;> class> MST {> >// Number of vertices in the graph> >static> int> V = 5;> >// A utility function to find> >// the vertex with minimum key> >// value, from the set of vertices> >// not yet included in MST> >static> int> minKey(>int>[] key,>bool>[] mstSet)> >{> >// Initialize min value> >int> min =>int>.MaxValue, min_index = -1;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in parent[] static void printMST(int[] parent, int[, ] graph) { Console.WriteLine('Edge Weight'); for (int i = 1; i Console.WriteLine(parent[i] + ' - ' + i + ' ' + graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[, ] graph) { // Array to store constructed MST int[] parent = new int[V]; // Key values used to pick // minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices // included in MST bool[] mstSet = new bool[V]; // Initialize all keys // as INFINITE for (int i = 0; i key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex // First node is always root of MST key[0] = 0; parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex // from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex // to the MST Set mstSet[u] = true; // Update key value and parent // index of the adjacent vertices // of the picked vertex. Consider // only those vertices which are // not yet included in MST for (int v = 0; v // graph[u][v] is non zero only // for adjacent vertices of m // mstSet[v] is false for vertices // not yet included in MST Update // the key only if graph[u][v] is // smaller than key[v] if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] parent[v] = u; key[v] = graph[u, v]; } } // Print the constructed MST printMST(parent, graph); } // Driver's Code public static void Main() { int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); } } // This code is contributed by anuj_67.> |
>
>
Javascript
> // Number of vertices in the graph> let V = 5;> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> function> minKey(key, mstSet)> {> >// Initialize min value> >let min = Number.MAX_VALUE, min_index;> >for> (let v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] function printMST(parent, graph) { document.write('Edge Weight' + ' '); for (let i = 1; i document.write(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]] + ' '); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation function primMST(graph) { // Array to store constructed MST let parent = []; // Key values used to pick minimum weight edge in cut let key = []; // To represent set of vertices included in MST let mstSet = []; // Initialize all keys as INFINITE for (let i = 0; i key[i] = Number.MAX_VALUE, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first vertex. key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (let count = 0; count { // Pick the minimum key vertex from the // set of vertices not yet included in MST let u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (let v = 0; v // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver code let graph = [ [ 0, 2, 0, 6, 0 ], [ 2, 0, 3, 8, 5 ], [ 0, 3, 0, 0, 7 ], [ 6, 8, 0, 0, 9 ], [ 0, 5, 7, 9, 0 ] ]; // Print the solution primMST(graph); // This code is contributed by Dharanendra L V.> |
>
>Produzione
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Analisi della complessità dell’algoritmo di Prim:
Complessità temporale: O(V2), Se l'input il grafico è rappresentato utilizzando una lista di adiacenza , allora la complessità temporale dell’algoritmo di Prim può essere ridotta a O(E * logV) con l’aiuto di un heap binario. In questa implementazione, consideriamo sempre lo spanning tree a partire dalla radice del grafico
Spazio ausiliario: O(V)
Altre implementazioni dell'algoritmo di Prim:
Di seguito sono riportate alcune altre implementazioni dell'algoritmo di Prim
- Algoritmo di Prim per la rappresentazione della matrice di adiacenza – In questo articolo abbiamo discusso il metodo di implementazione dell’Algoritmo di Prim se il grafico è rappresentato da una matrice di adiacenza.
- Algoritmo di Prim per la rappresentazione di liste di adiacenze – In questo articolo viene descritta l’implementazione dell’algoritmo di Prim per grafi rappresentati da una lista di adiacenze.
- Algoritmo di Prim che utilizza la coda prioritaria: In questo articolo, abbiamo discusso un approccio efficiente in termini di tempo per implementare l’algoritmo di Prim.
APPROCCIO OTTIMIZZATO DELL'ALGORITMO DI PRIM:
Intuizione
- Trasformiamo la matrice di adiacenza in lista di adiacenza utilizzando Lista di array
. - Quindi creiamo una classe Pair per memorizzare il vertice e il suo peso.
- Ordiniamo l'elenco in base al peso più basso.
- Creiamo una coda prioritaria e inseriamo il primo vertice e il suo peso nella coda
- Quindi attraversiamo semplicemente i suoi bordi e memorizziamo il peso minimo in una variabile chiamata anni.
- Alla fine dopo tutto il vertice restituiamo l'ans.
Implementazione
C++
allinea l'immagine CSS
#include> using> namespace> std;> typedef> pair<>int>,>int>>pii;> // Function to find sum of weights of edges of the Minimum Spanning Tree.> int> spanningTree(>int> V,>int> E,>int> edges[][3])> {> >// Create an adjacency list representation of the graph> >vectorint>> agg[V]; // Riempie la lista di adiacenza con i bordi e i loro pesi per (int i = 0; i int u = bordi[i][0]; int v = bordi[i][1]; int wt = bordi[i][2 ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); // Crea una coda con priorità per memorizzare gli edge con i loro pesi priorità_queue pq; array visitato per tenere traccia del vettore dei vertici visitati |
>
>
Giava
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency list> // representation of the graph> import> java.io.*;> import> java.util.*;> // Class to form pair> class> Pair>implements> Comparable> {> >int> v;> >int> wt;> >Pair(>int> v,>int> wt)> >{> >this>.v=v;> >this>.wt=wt;> >}> >public> int> compareTo(Pair that)> >{> >return> this>.wt-that.wt;> >}> }> class> GFG {> // Function of spanning tree> static> int> spanningTree(>int> V,>int> E,>int> edges[][])> >{> >ArrayList adj=>new> ArrayList();> >for>(>int> i=>0>;i { adj.add(new ArrayList()); } for(int i=0;i { int u=edges[i][0]; int v=edges[i][1]; int wt=edges[i][2]; adj.get(u).add(new Pair(v,wt)); adj.get(v).add(new Pair(u,wt)); } PriorityQueue pq = new PriorityQueue(); pq.add(new Pair(0,0)); int[] vis=new int[V]; int s=0; while(!pq.isEmpty()) { Pair node=pq.poll(); int v=node.v; int wt=node.wt; if(vis[v]==1) continue; s+=wt; vis[v]=1; for(Pair it:adj.get(v)) { if(vis[it.v]==0) { pq.add(new Pair(it.v,it.wt)); } } } return s; } // Driver code public static void main (String[] args) { int graph[][] = new int[][] {{0,1,5}, {1,2,3}, {0,2,1}}; // Function call System.out.println(spanningTree(3,3,graph)); } }> |
>
>
Python3
import> heapq> def> tree(V, E, edges):> ># Create an adjacency list representation of the graph> >adj>=> [[]>for> _>in> range>(V)]> ># Fill the adjacency list with edges and their weights> >for> i>in> range>(E):> >u, v, wt>=> edges[i]> >adj[u].append((v, wt))> >adj[v].append((u, wt))> ># Create a priority queue to store edges with their weights> >pq>=> []> ># Create a visited array to keep track of visited vertices> >visited>=> [>False>]>*> V> ># Variable to store the result (sum of edge weights)> >res>=> 0> ># Start with vertex 0> >heapq.heappush(pq, (>0>,>0>))> ># Perform Prim's algorithm to find the Minimum Spanning Tree> >while> pq:> >wt, u>=> heapq.heappop(pq)> >if> visited[u]:> >continue> ># Skip if the vertex is already visited> >res>+>=> wt> ># Add the edge weight to the result> >visited[u]>=> True> ># Mark the vertex as visited> ># Explore the adjacent vertices> >for> v, weight>in> adj[u]:> >if> not> visited[v]:> >heapq.heappush(pq, (weight, v))> ># Add the adjacent edge to the priority queue> >return> res> ># Return the sum of edge weights of the Minimum Spanning Tree> if> __name__>=>=> '__main__'>:> >graph>=> [[>0>,>1>,>5>],> >[>1>,>2>,>3>],> >[>0>,>2>,>1>]]> ># Function call> >print>(tree(>3>,>3>, graph))> |
>
>
C#
using> System;> using> System.Collections.Generic;> public> class> MinimumSpanningTree> {> >// Function to find sum of weights of edges of the Minimum Spanning Tree.> >public> static> int> SpanningTree(>int> V,>int> E,>int>[,] edges)> >{> >// Create an adjacency list representation of the graph> >Listint[]>> adj = nuovo Listint[]>>(); for (int i = 0; i { adj.Add(new List |
>
>
Javascript
class PriorityQueue {> >constructor() {> >this>.heap = [];> >}> >enqueue(value) {> >this>.heap.push(value);> >let i =>this>.heap.length - 1;> >while> (i>0) {> >let j = Math.floor((i - 1) / 2);> >if> (>this>.heap[i][0]>=>this>.heap[j][0]) {> >break>;> >}> >[>this>.heap[i],>this>.heap[j]] = [>this>.heap[j],>this>.heap[i]];> >i = j;> >}> >}> >dequeue() {> >if> (>this>.heap.length === 0) {> >throw> new> Error(>'Queue is empty'>);> >}> >let i =>this>.heap.length - 1;> >const result =>this>.heap[0];> >this>.heap[0] =>this>.heap[i];> >this>.heap.pop();> >i--;> >let j = 0;> >while> (>true>) {> >const left = j * 2 + 1;> >if> (left>i) {> >break>;> >}> >const right = left + 1;> >let k = left;> >if> (right <= i &&>this>.heap[right][0] <>this>.heap[left][0]) {> >k = right;> >}> >if> (>this>.heap[j][0] <=>this>.heap[k][0]) {> >break>;> >}> >[>this>.heap[j],>this>.heap[k]] = [>this>.heap[k],>this>.heap[j]];> >j = k;> >}> >return> result;> >}> >get count() {> >return> this>.heap.length;> >}> }> function> spanningTree(V, E, edges) {> >// Create an adjacency list representation of the graph> >const adj =>new> Array(V).fill(>null>).map(() =>[]);> >// Fill the adjacency list with edges and their weights> >for> (let i = 0; i const [u, v, wt] = edges[i]; adj[u].push([v, wt]); adj[v].push([u, wt]); } // Create a priority queue to store edges with their weights const pq = new PriorityQueue(); // Create a visited array to keep track of visited vertices const visited = new Array(V).fill(false); // Variable to store the result (sum of edge weights) let res = 0; // Start with vertex 0 pq.enqueue([0, 0]); // Perform Prim's algorithm to find the Minimum Spanning Tree while (pq.count>0) { const p = pq.dequeue(); const peso = p[0]; // Peso del bordo const u = p[1]; // Vertice connesso al bordo if (visited[u]) { continue; // Salta se il vertice è già visitato } res += wt; // Aggiungi lo spessore del bordo al risultato visitato[u] = true; // Segna il vertice come visitato // Esplora i vertici adiacenti per (const v of adj[u]) { // v[0] rappresenta il vertice e v[1] rappresenta il peso del bordo if (!visited[v[0 ]]) { pq.enqueue([v[1], v[0]]); // Aggiunge il bordo adiacente alla coda con priorità } } } return res; // Restituisce la somma dei pesi dei bordi del Minimum Spanning Tree } // Esempio di utilizzo const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Chiamata di funzione console.log(spanningTree(3, 3, graph));> |
>
>Produzione
4>
Analisi della complessità dell’algoritmo di Prim:
Complessità temporale: O(E*log(E)) dove E è il numero di archi
Spazio ausiliario: O(V^2) dove V è il numero di vertici
Algoritmo di Prim per trovare l'albero di copertura minimo (MST):
Vantaggi:
- L’algoritmo di Prim è sicuro di trovare l’MST in un grafico connesso e ponderato.
- Ha una complessità temporale di O(E log V) utilizzando un heap binario o heap di Fibonacci, dove E è il numero di spigoli e V è il numero di vertici.
- È un algoritmo relativamente semplice da comprendere e implementare rispetto ad altri algoritmi MST.
Svantaggi:
- Come l’algoritmo di Kruskal, l’algoritmo di Prim può essere lento su grafici densi con molti spigoli, poiché richiede l’iterazione su tutti gli spigoli almeno una volta.
- L’algoritmo di Prim si basa su una coda di priorità, che può occupare memoria extra e rallentare l’algoritmo su grafici molto grandi.
- La scelta del nodo iniziale può influenzare l'output MST, il che potrebbe non essere desiderabile in alcune applicazioni.