Introduktion til Prims algoritme:
Vi har diskuteret Kruskals algoritme for Minimum Spanning Tree . Ligesom Kruskals algoritme er Prims algoritme også en Grådig algoritme . Denne algoritme starter altid med en enkelt node og bevæger sig gennem flere tilstødende noder for at udforske alle de forbundne kanter undervejs.
Algoritmen starter med et tomt spændingstræ. Ideen er at opretholde to sæt toppunkter. Det første sæt indeholder de hjørner, der allerede er inkluderet i MST, og det andet sæt indeholder de hjørner, der endnu ikke er inkluderet. Ved hvert trin tager den hensyn til alle de kanter, der forbinder de to sæt, og vælger minimumvægtkanten fra disse kanter. Efter at have valgt kanten, flytter den det andet endepunkt af kanten til sættet, der indeholder MST.
En gruppe kanter, der forbinder to sæt toppunkter i en graf, kaldes skære i grafteori . Så ved hvert trin af Prims algoritme skal du finde et snit, vælge minimumvægtkanten fra snittet og inkludere dette toppunkt i MST Set (sættet, der indeholder allerede inkluderede hjørner).
Hvordan virker Prims algoritme?
Funktionen af Prims algoritme kan beskrives ved at bruge følgende trin:
Trin 1: Bestem et vilkårligt vertex som startpunktet for MST.
Trin 2: Følg trin 3 til 5, indtil der er hjørner, der ikke er inkluderet i MST (kendt som fringe vertex).
Trin 3: Find kanter, der forbinder ethvert trætop med frynser.
Trin 4: Find minimum blandt disse kanter.
Trin 5: Tilføj den valgte kant til MST, hvis den ikke danner nogen cyklus.
Trin 6: Returner MST og forlad
Bemærk: For at bestemme en cyklus kan vi opdele hjørnerne i to sæt [et sæt indeholder hjørnerne inkluderet i MST, og det andet indeholder randhjørnerne.]
Anbefalet praksis Minimum Spanning Tree Prøv det!Illustration af Prims algoritme:
Betragt følgende graf som et eksempel, hvor vi skal finde Minimum Spanning Tree (MST).
Eksempel på en graf
Trin 1: For det første vælger vi et vilkårligt toppunkt, der fungerer som startpunktet for minimumsspændingstræet. Her har vi valgt toppunkt 0 som startpunkt.
0 er valgt som startpunkt
Trin 2: Alle de kanter, der forbinder den ufuldstændige MST og andre hjørner, er kanterne {0, 1} og {0, 7}. Mellem disse to er kanten med minimumvægt {0, 1}. Så medtag kanten og toppunktet 1 i MST.
1 tilføjes til MST
Trin 3: Kanterne, der forbinder den ufuldstændige MST til andre hjørner, er {0, 7}, {1, 7} og {1, 2}. Blandt disse kanter er minimumvægten 8, hvilket er af kanterne {0, 7} og {1, 2}. Lad os her inkludere kanten {0, 7} og toppunktet 7 i MST. [Vi kunne også have inkluderet kant {1, 2} og toppunkt 2 i MST].
7 er tilføjet i MST
Trin 4: Kanterne, der forbinder den ufuldstændige MST med randhjørnerne, er {1, 2}, {7, 6} og {7, 8}. Tilføj kanten {7, 6} og toppunktet 6 i MST, da det har den mindste vægt (dvs. 1).
6 er tilføjet i MST
Trin 5: Forbindelseskanterne er nu {7, 8}, {1, 2}, {6, 8} og {6, 5}. Inkluder kant {6, 5} og toppunkt 5 i MST, da kanten har den mindste vægt (dvs. 2) blandt dem.
Inkluder toppunkt 5 i MST
Trin 6: Blandt de nuværende forbindelseskanter har kanten {5, 2} minimumvægten. Så medtag den kant og toppunktet 2 i MST.
Inkluder toppunkt 2 i MST
Trin 7: Forbindelseskanterne mellem den ufuldstændige MST og de andre kanter er {2, 8}, {2, 3}, {5, 3} og {5, 4}. Kanten med minimumvægt er kant {2, 8}, som har vægt 2. Så inkluder denne kant og toppunktet 8 i MST.
Tilføj toppunkt 8 i MST
Trin 8: Se her, at kanterne {7, 8} og {2, 3} begge har samme vægt, som er minimum. Men 7 er allerede en del af MST. Så vi vil overveje kanten {2, 3} og inkludere den kant og toppunkt 3 i MST.
Inkluder toppunkt 3 i MST
Trin 9: Kun toppunktet 4 skal inkluderes. Den mindste vægtede kant fra den ufuldstændige MST til 4 er {3, 4}.
Inkluder toppunkt 4 i MST
Den endelige struktur af MST er som følger, og vægten af kanterne af MST er (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
Strukturen af MST dannet ved hjælp af ovenstående metode
Bemærk: Hvis vi havde valgt kanten {1, 2} i det tredje trin, ville MST se ud som følgende.
Struktur af den alternative MST, hvis vi havde valgt kant {1, 2} i MST
Hvordan implementerer man Prims algoritme?
Følg de givne trin for at bruge Prims algoritme nævnt ovenfor for at finde MST af en graf:
- Opret et sæt mstSet der holder styr på hjørner, der allerede er inkluderet i MST.
- Tildel en nøgleværdi til alle hjørner i inputgrafen. Initialiser alle nøgleværdier som UENDELIG. Tildel nøgleværdien som 0 for det første toppunkt, så det vælges først.
- Mens mstSet omfatter ikke alle hjørner
- Vælg et toppunkt i det er der ikke i mstSet og har en minimumsnøgleværdi.
- Omfatte i i mstSet .
- Opdater nøgleværdien for alle tilstødende hjørner af i . For at opdatere nøgleværdierne, gentag gennem alle tilstødende hjørner.
- For hvert tilstødende toppunkt i , hvis vægten af kant u-v er mindre end den forrige nøgleværdi af i , opdater nøgleværdien som vægten af u-v .
Ideen med at bruge nøgleværdier er at vælge minimumvægtkanten fra skære . Nøgleværdierne bruges kun for knudepunkter, der endnu ikke er inkluderet i MST, nøgleværdien for disse knudepunkter angiver minimumsvægtkanterne, der forbinder dem med det sæt af knudepunkter, der er inkluderet i MST.
Nedenfor er implementeringen af tilgangen:
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> |
>
linux omdøb mappe
>
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> |
>
>
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>
Kompleksitetsanalyse af Prims algoritme:
Tidskompleksitet: O(V2), Hvis input grafen er repræsenteret ved hjælp af en tilgrænsende liste , så kan tidskompleksiteten af Prims algoritme reduceres til O(E * logV) ved hjælp af en binær heap. I denne implementering overvejer vi altid, at spændingstræet starter fra grafens rod
Hjælpeplads: O(V)
Andre implementeringer af Prims algoritme:
Nedenfor er nogle andre implementeringer af Prims algoritme
- Prims algoritme for adjacency matrix repræsentation – I denne artikel har vi diskuteret metoden til at implementere Prims algoritme, hvis grafen er repræsenteret af en tilstødende matrix.
- Prims algoritme for tilgrænsende listerepræsentation – I denne artikel er Prims algoritmeimplementering beskrevet for grafer repræsenteret af en tilgrænsende liste.
- Prims algoritme ved hjælp af Priority Queue: I denne artikel har vi diskuteret en tidseffektiv tilgang til implementering af Prims algoritme.
OPTIMERET TILGANG TIL PRIM'S ALGORITIME:
Intuition
- Vi omdanner adjacency-matricen til adjacency-liste vha ArrayList
. - Derefter opretter vi en parklasse for at gemme toppunktet og dets vægt.
- Vi sorterer listen ud fra laveste vægt.
- Vi opretter prioritetskø og skubber det første toppunkt og dets vægt i køen
- Så krydser vi bare gennem dens kanter og gemmer den mindste vægt i en variabel kaldet flere år.
- Til sidst efter hele toppunktet returnerer vi ans.
Implementering
C++
navne på byer i USA
#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]; // Udfyld listen over tilstødende med kanter og deres vægte for (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øgt array for at holde styr på besøgte toppunkter vektor |
>
>
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 liste |
>
>
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]; // Vægt af kantkonst u = p[1]; // Vertex forbundet med kanten if (besøgt[u]) { continue; // Spring over hvis toppunktet allerede er besøgt } res += wt; // Tilføj kantvægten til det besøgte resultat[u] = sand; // Marker toppunktet som besøgt // Udforsk de tilstødende toppunkter for (konst v af adj[u]) { // v[0] repræsenterer toppunktet og v[1] repræsenterer kantvægten hvis (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Tilføj den tilstødende kant til prioritetskøen } } } return res; // Returner summen af kantvægte af Minimum Spanning Tree } // Eksempel på brugskonst graf = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Funktionskald console.log(spanningTree(3, 3, graf));> |
>
>Produktion
4>
Kompleksitetsanalyse af Prims algoritme:
Tidskompleksitet: O(E*log(E)), hvor E er antallet af kanter
Hjælpeplads: O(V^2) hvor V er antallet af toppunkter
Prims algoritme til at finde minimumspændingstræet (MST):
Fordele:
- Prims algoritme vil med garanti finde MST i en forbundet, vægtet graf.
- Den har en tidskompleksitet på O(E log V) ved hjælp af en binær hob eller Fibonacci-dynge, hvor E er antallet af kanter, og V er antallet af hjørner.
- Det er en forholdsvis simpel algoritme at forstå og implementere sammenlignet med nogle andre MST-algoritmer.
Ulemper:
- Ligesom Kruskals algoritme kan Prims algoritme være langsom på tætte grafer med mange kanter, da den kræver iteration over alle kanter mindst én gang.
- Prims algoritme er afhængig af en prioritetskø, som kan optage ekstra hukommelse og bremse algoritmen på meget store grafer.
- Valget af startnode kan påvirke MST-outputtet, hvilket måske ikke er ønskeligt i nogle applikationer.