Introduktion till Prims algoritm:
Vi har diskuterat Kruskals algoritm för Minimum Spanning Tree . Liksom Kruskals algoritm är Prims algoritm också en Girig algoritm . Denna algoritm börjar alltid med en enda nod och rör sig genom flera intilliggande noder, för att utforska alla anslutna kanter längs vägen.
Algoritmen börjar med ett tomt spännträd. Tanken är att behålla två uppsättningar av hörn. Den första uppsättningen innehåller de hörn som redan ingår i MST, och den andra uppsättningen innehåller de hörn som ännu inte ingår. Vid varje steg tar den hänsyn till alla kanter som förbinder de två uppsättningarna och väljer den minsta viktkanten från dessa kanter. Efter att ha valt kanten flyttar den den andra ändpunkten av kanten till uppsättningen som innehåller MST.
En grupp av kanter som förbinder två uppsättningar av hörn i en graf kallas skär i grafteori . Så, vid varje steg i Prims algoritm, hitta ett snitt, välj den minsta viktkanten från snittet och inkludera denna vertex i MST Set (uppsättningen som innehåller redan inkluderade hörn).
Hur fungerar Prims algoritm?
Funktionen av Prims algoritm kan beskrivas genom att använda följande steg:
Steg 1: Bestäm en godtycklig vertex som startpunkten för MST.
Steg 2: Följ steg 3 till 5 tills det finns hörn som inte ingår i MST (känd som fringe vertex).
Steg 3: Leta reda på kanter som förbinder valfritt trädspunkt med franskanterna.
Steg 4: Hitta minimum bland dessa kanter.
Steg 5: Lägg till den valda kanten till MST om den inte bildar någon cykel.
Steg 6: Lämna tillbaka MST och avsluta
Notera: För att bestämma en cykel kan vi dela upp hörnen i två uppsättningar [den ena uppsättningen innehåller de hörn som ingår i MST och den andra innehåller franshörnen.]
Rekommenderad praxis Minsta spännande träd Prova det!Illustration av Prims algoritm:
Betrakta följande graf som ett exempel för vilket vi måste hitta Minimum Spanning Tree (MST).
Exempel på en graf
Steg 1: Först väljer vi en godtycklig vertex som fungerar som startpunkten för det minimala spännträdet. Här har vi valt vertex 0 som startpunkt.
0 väljs som startpunkt
Steg 2: Alla kanter som förbinder den ofullständiga MST och andra hörn är kanterna {0, 1} och {0, 7}. Mellan dessa två är kanten med minsta vikt {0, 1}. Så inkludera kanten och vertex 1 i MST.
1 läggs till MST
Steg 3: Kanterna som förbinder den ofullständiga MST med andra hörn är {0, 7}, {1, 7} och {1, 2}. Bland dessa kanter är minimivikten 8, vilket är av kanterna {0, 7} och {1, 2}. Låt oss här inkludera kanten {0, 7} och vertex 7 i MST. [Vi kunde också ha inkluderat kant {1, 2} och vertex 2 i MST].
7 läggs till i MST
Steg 4: Kanterna som förbinder den ofullständiga MST med franshörnen är {1, 2}, {7, 6} och {7, 8}. Lägg till kanten {7, 6} och vertex 6 i MST eftersom den har minst vikt (dvs. 1).
6 läggs till i MST
Steg 5: Förbindningskanterna är nu {7, 8}, {1, 2}, {6, 8} och {6, 5}. Inkludera kant {6, 5} och vertex 5 i MST eftersom kanten har minsta vikt (dvs. 2) bland dem.
Inkludera vertex 5 i MST
Steg 6: Bland de nuvarande anslutningskanterna har kanten {5, 2} minsta vikt. Så inkludera den kanten och vertex 2 i MST.
Inkludera vertex 2 i MST
Steg 7: Förbindningskanterna mellan den ofullständiga MST och de andra kanterna är {2, 8}, {2, 3}, {5, 3} och {5, 4}. Kanten med minsta vikt är kant {2, 8} som har vikt 2. Så inkludera denna kant och vertex 8 i MST.
Lägg till vertex 8 i MST
Steg 8: Se här att kanterna {7, 8} och {2, 3} båda har samma vikt som är minsta. Men 7 är redan en del av MST. Så vi kommer att betrakta kanten {2, 3} och inkludera den kanten och vertex 3 i MST.
Inkludera vertex 3 i MST
Steg 9: Endast vertex 4 återstår att inkludera. Den minsta viktade kanten från den ofullständiga MST till 4 är {3, 4}.
Inkludera vertex 4 i MST
Den slutliga strukturen för MST är som följer och vikten av kanterna på MST är (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
Strukturen av MST bildad med användning av ovanstående metod
123 filmNotera: Om vi hade valt kanten {1, 2} i det tredje steget skulle MST se ut så här.
Strukturen för den alternativa MST om vi hade valt kant {1, 2} i MST
Hur implementerar man Prims algoritm?
Följ de givna stegen för att använda Prims algoritm nämns ovan för att hitta MST för en graf:
- Skapa ett set mstSet som håller reda på hörn som redan ingår i MST.
- Tilldela ett nyckelvärde till alla hörn i inmatningsdiagrammet. Initiera alla nyckelvärden som INFINITE. Tilldela nyckelvärdet som 0 för det första hörnet så att det väljs först.
- Medan mstSet inkluderar inte alla hörn
- Välj en vertex i som inte finns där mstSet och har ett lägsta nyckelvärde.
- Omfatta i i mstSet .
- Uppdatera nyckelvärdet för alla intilliggande hörn av i . För att uppdatera nyckelvärdena, iterera genom alla intilliggande hörn.
- För varje intilliggande vertex i , om vikten av kant u-v är mindre än det föregående nyckelvärdet på i , uppdatera nyckelvärdet som vikten av u-v .
Tanken med att använda nyckelvärden är att välja den lägsta viktkanten från skära . Nyckelvärdena används endast för hörn som ännu inte ingår i MST, nyckelvärdet för dessa hörn indikerar de minsta viktkanterna som ansluter dem till uppsättningen av hörn som ingår i MST.
Nedan är implementeringen av tillvägagångssättet:
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 int till dubbel
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> |
>
>
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.> |
>
>Produktion
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Komplexitetsanalys av Prims algoritm:
Tidskomplexitet: O(V2), Om ingången grafen representeras med hjälp av en angränsande lista , då kan tidskomplexiteten för Prims algoritm reduceras till O(E * logV) med hjälp av en binär hög. I den här implementeringen överväger vi alltid att spännträdet ska börja från roten av grafen
Hjälputrymme: O(V)
Andra implementeringar av Prims algoritm:
Nedan finns några andra implementeringar av Prims algoritm
- Prims algoritm för närliggande matrisrepresentation – I den här artikeln har vi diskuterat metoden för att implementera Prims algoritm om grafen representeras av en närliggande matris.
- Prim's Algorithm for Adjacency List Representation – I den här artikeln beskrivs Prims algoritmimplementering för grafer som representeras av en angränsande lista.
- Prims algoritm som använder Priority Queue: I den här artikeln har vi diskuterat ett tidseffektivt tillvägagångssätt för att implementera Prims algoritm.
OPTIMERAD ANVÄNDNING AV PRIM:S ALGORITM:
Intuition
- Vi omvandlar angränsningsmatrisen till angränsningslista med hjälp av ArrayList
. - Sedan skapar vi en parklass för att lagra vertex och dess vikt.
- Vi sorterar listan efter lägsta vikt.
- Vi skapar prioriterad kö och trycker in den första vertexen och dess vikt i kön
- Sedan går vi bara genom dess kanter och lagrar minsta vikt i en variabel som kallas år.
- Äntligen efter alla vertex returnerar vi ans.
Genomförande
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]; // Fyll grannlistan med kanter och deras vikter för (int i = 0; i int u = kanter[i][0]; int v = kanter[i][1]; int wt = kanter[i][2); ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); besökt array för att hålla reda på vektorn för besökta hörn |
>
>
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)); } }> |
>
>
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 = new Listint[]>>(); for (int i = 0; i { adj.Add(ny lista |
>
>
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]; // Kantens vikt konst u = p[1]; // Vertex kopplat till kanten if (besökt[u]) { continue; // Hoppa över om vertexet redan är besökt } res += wt; // Lägg till kantvikten till det besökta resultatet[u] = sant; // Markera vertex som besökt // Utforska de intilliggande hörnen för (konst v av adj[u]) { // v[0] representerar vertexet och v[1] representerar kantvikten om (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Lägg till den intilliggande kanten till prioritetskön } } } return res; // Returnera summan av kantvikter för trädet med minsta spännvidd } // Exempel på användningskonst graf = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Funktionsanrop console.log(spanningTree(3, 3, graph));> |
>
1 miljard till miljon
>Produktion
4>
Komplexitetsanalys av Prims algoritm:
Tidskomplexitet: O(E*log(E)) där E är antalet kanter
Hjälputrymme: O(V^2) där V är numret på vertex
Prims algoritm för att hitta minsta spännträd (MST):
Fördelar:
- Prims algoritm kommer garanterat att hitta MST i en sammankopplad, viktad graf.
- Den har en tidskomplexitet av O(E log V) med en binär hög eller Fibonacci-hög, där E är antalet kanter och V är antalet hörn.
- Det är en relativt enkel algoritm att förstå och implementera jämfört med vissa andra MST-algoritmer.
Nackdelar:
- Precis som Kruskals algoritm kan Prims algoritm vara långsam på täta grafer med många kanter, eftersom den kräver iteration över alla kanter minst en gång.
- Prims algoritm förlitar sig på en prioritetskö, som kan ta upp extra minne och sakta ner algoritmen på mycket stora grafer.
- Valet av startnod kan påverka MST-utgången, vilket kanske inte är önskvärt i vissa applikationer.