Introducció a l'algorisme de Prim:
Hem comentat L'algorisme de Kruskal per a l'arbre d'abast mínim . Igual que l'algoritme de Kruskal, l'algoritme de Prim també és a Algoritme cobdiciós . Aquest algorisme sempre comença amb un sol node i es mou per diversos nodes adjacents, per tal d'explorar totes les vores connectades al llarg del camí.
L'algorisme comença amb un arbre d'abast buit. La idea és mantenir dos conjunts de vèrtexs. El primer conjunt conté els vèrtexs ja inclosos al MST, i l'altre conjunt conté els vèrtexs encara no inclosos. A cada pas, considera totes les vores que connecten els dos conjunts i tria la vora de pes mínim d'aquestes vores. Després de triar la vora, mou l'altre punt final de la vora al conjunt que conté MST.
S'anomena un grup d'arestes que connecta dos conjunts de vèrtexs en un gràfic tall en teoria de grafs . Per tant, a cada pas de l'algorisme de Prim, trobeu un tall, trieu la vora de pes mínim del tall i incloeu aquest vèrtex al conjunt MST (el conjunt que conté vèrtexs ja inclosos).
Com funciona l'algoritme de Prim?
El funcionament de l'algorisme de Prim es pot descriure mitjançant els passos següents:
Pas 1: Determineu un vèrtex arbitrari com a vèrtex inicial del MST.
Pas 2: Seguiu els passos del 3 al 5 fins que hi hagi vèrtexs que no s'incloguin al MST (conegut com a vèrtex marginal).
Pas 3: Trobeu vores que connectin qualsevol vèrtex de l'arbre amb els vèrtexs de la franja.
Pas 4: Trobeu el mínim entre aquestes vores.
Pas 5: Afegiu l'aresta escollida al MST si no forma cap cicle.
Pas 6: Torna el MST i surt
Nota: Per determinar un cicle, podem dividir els vèrtexs en dos conjunts [un conjunt conté els vèrtexs inclosos a MST i l'altre conté els vèrtexs marginals.]
Pràctica recomanada Spanning Tree mínim Prova-ho!Il·lustració de l'algoritme de Prim:
Considereu el gràfic següent com un exemple per al qual hem de trobar l'arbre d'abast mínim (MST).
Exemple de gràfic
Pas 1: En primer lloc, seleccionem un vèrtex arbitrari que actua com a vèrtex inicial de l'arbre d'abast mínim. Aquí hem seleccionat el vèrtex 0 com a vèrtex inicial.
S'ha seleccionat 0 com a vèrtex inicial
Pas 2: Totes les arestes que connecten el MST incomplet i altres vèrtexs són les arestes {0, 1} i {0, 7}. Entre aquests dos, la vora amb pes mínim és {0, 1}. Per tant, inclou l'aresta i el vèrtex 1 al MST.
1 s'afegeix al MST
Pas 3: Les arestes que connecten el MST incomplet amb altres vèrtexs són {0, 7}, {1, 7} i {1, 2}. Entre aquestes arestes el pes mínim és 8, que és de les arestes {0, 7} i {1, 2}. Incloem aquí l'aresta {0, 7} i el vèrtex 7 al MST. [També podríem haver inclòs l'aresta {1, 2} i el vèrtex 2 al MST].
7 s'afegeix al MST
Pas 4: Les arestes que connecten el MST incomplet amb els vèrtexs marginals són {1, 2}, {7, 6} i {7, 8}. Afegiu l'aresta {7, 6} i el vèrtex 6 al MST, ja que té el menor pes (és a dir, 1).
6 s'afegeix al MST
Pas 5: Les vores de connexió ara són {7, 8}, {1, 2}, {6, 8} i {6, 5}. Inclou l'aresta {6, 5} i el vèrtex 5 al MST, ja que l'aresta té el pes mínim (és a dir, 2) entre ells.
Inclou el vèrtex 5 al MST
Pas 6: Entre les vores de connexió actuals, la vora {5, 2} té el pes mínim. Per tant, inclou aquesta vora i el vèrtex 2 al MST.
Inclou el vèrtex 2 al MST
Pas 7: Les vores de connexió entre el MST incomplet i les altres arestes són {2, 8}, {2, 3}, {5, 3} i {5, 4}. L'aresta amb pes mínim és l'aresta {2, 8} que té un pes 2. Per tant, inclou aquesta aresta i el vèrtex 8 al MST.
Afegiu el vèrtex 8 al MST
Pas 8: Vegeu aquí que les arestes {7, 8} i {2, 3} tenen el mateix pes que són mínims. Però 7 ja forma part de MST. Així doncs, considerarem l'aresta {2, 3} i inclourem aquesta aresta i el vèrtex 3 al MST.
Inclou el vèrtex 3 a MST
Pas 9: Només queda per incloure el vèrtex 4. La vora ponderada mínima des del MST incomplet fins a 4 és {3, 4}.
Inclou el vèrtex 4 al MST
L'estructura final del MST és la següent i el pes de les vores del MST és (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
L'estructura del MST es va formar mitjançant el mètode anterior
Nota: Si haguéssim seleccionat la vora {1, 2} al tercer pas, l'MST tindria un aspecte semblant al següent.
Estructura del MST alternatiu si haguéssim seleccionat la vora {1, 2} al MST
Com implementar l'algoritme de Prim?
Seguiu els passos indicats per utilitzar el Algoritme de Prim esmentat anteriorment per trobar MST d'un gràfic:
- Crea un conjunt mstSet que fa un seguiment dels vèrtexs ja inclosos a MST.
- Assigna un valor clau a tots els vèrtexs del gràfic d'entrada. Inicialitzeu tots els valors clau com a INFINIT. Assigna el valor de la clau com a 0 per al primer vèrtex perquè s'esculli primer.
- Mentre mstSet no inclou tots els vèrtexs
- Trieu un vèrtex en que no hi és mstSet i té un valor de clau mínim.
- Incloure en en el mstSet .
- Actualitzeu el valor clau de tots els vèrtexs adjacents de en . Per actualitzar els valors clau, itereu per tots els vèrtexs adjacents.
- Per a cada vèrtex adjacent en , si el pes de la vora u-v és inferior al valor de clau anterior de en , actualitzeu el valor de la clau com a pes de u-v .
La idea d'utilitzar valors clau és escollir la vora de pes mínim del tallar . Els valors clau només s'utilitzen per als vèrtexs que encara no estan inclosos a MST, el valor clau per a aquests vèrtexs indica les vores de pes mínim que els connecten amb el conjunt de vèrtexs inclòs en MST.
A continuació es mostra la implementació de l'enfocament:
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> |
>
>
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; }> |
>
>
Java
// 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> |
>
>
Python 3
# 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.> |
>
>Sortida
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Anàlisi de complexitat de l'algoritme de Prim:
Complexitat temporal: O (V2), Si l'entrada El gràfic es representa mitjançant una llista d'adjacència , aleshores la complexitat temporal de l'algorisme de Prim es pot reduir a O(E * logV) amb l'ajuda d'un munt binari. En aquesta implementació, sempre estem considerant que l'arbre spanning comença des de l'arrel del gràfic
Espai auxiliar: O(V)
Altres implementacions de l'algoritme de Prim:
A continuació es mostren algunes altres implementacions de l'algoritme de Prim
- Algoritme de Prim per a la representació de matrius d'adjacència – En aquest article hem parlat del mètode d'implementació de l'algoritme de Prim si el gràfic es representa amb una matriu d'adjacència.
- Algoritme de Prim per a la representació de la llista d'adjacència – En aquest article es descriu la implementació de l'algoritme de Prim per a gràfics representats per una llista d'adjacència.
- Algorisme de Prim utilitzant la cua de prioritats: En aquest article, hem parlat d'un enfocament eficient en temps per implementar l'algorisme de Prim.
ENFOCAMENT OPTIMITZAT DE L'ALGORITME DE PRIM:
Intuïció
- Transformem la matriu d'adjacència en llista d'adjacència utilitzant ArrayList
. - Aleshores creem una classe Pair per emmagatzemar el vèrtex i el seu pes.
- Ordenam la llista en funció del pes més baix.
- Creem la cua de prioritats i empenyem el primer vèrtex i el seu pes a la cua
- Aleshores només travessem les seves vores i emmagatzemem el menor pes en una variable anomenada anys.
- Per fi després de tot el vèrtex tornem l'ans.
Implementació
C++
#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>> adj[V]; // Omple la llista d'adjacència amb arestes i els seus pesos per a (int i = 0; i int u = arestes[i][0]; int v = arestes[i][1]; int wt = arestes[i][2] ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); matriu visitada per fer un seguiment del vector de vèrtexs visitat |
>
>
Java
// 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)); } }> |
>
>
Python 3
java amb swing
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 = nou Listint[]>>(); for (int i = 0; i { adj.Add (nou llista |
>
>
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 wt = p[0]; // Pes de la vora const u = p[1]; // Vèrtex connectat a la vora if (visited[u]) { continue; // Omet si el vèrtex ja està visitat } res += wt; // Afegeix el pes de la vora al resultat visitat[u] = true; // Marca el vèrtex com a visitat // Explora els vèrtexs adjacents per a (const v de adj[u]) { // v[0] representa el vèrtex i v[1] representa el pes de la vora si (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Afegeix la vora adjacent a la cua de prioritats } } } return res; // Retorna la suma dels pesos de les vores de l'arbre d'abast mínim } // Exemple de gràfic const d'ús = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Crida a la funció console.log(spanningTree(3, 3, graph));>>> |
>4>
Anàlisi de complexitat de l'algoritme de Prim:
Complexitat temporal: O(E*log(E)) on E és el nombre d'arestes
Espai auxiliar: O(V^2) on V és el nombre de vèrtex
Algorisme de Prim per trobar l'arbre d'abast mínim (MST):
Avantatges:
- L'algorisme de Prim està garantit per trobar el MST en un gràfic connectat i ponderat.
- Té una complexitat temporal de O(E log V) utilitzant un munt binari o un munt de Fibonacci, on E és el nombre d'arestes i V és el nombre de vèrtexs.
- És un algorisme relativament senzill d'entendre i implementar en comparació amb altres algorismes MST.
Desavantatges:
- Igual que l'algorisme de Kruskal, l'algoritme de Prim pot ser lent en gràfics densos amb moltes arestes, ja que requereix iterar sobre totes les arestes almenys una vegada.
- L'algorisme de Prim es basa en una cua de prioritat, que pot ocupar memòria addicional i alentir l'algorisme en gràfics molt grans.
- L'elecció del node inicial pot afectar la sortida MST, cosa que pot no ser desitjable en algunes aplicacions.