Inleiding tot het algoritme van Prim:
We hebben besproken Kruskal's algoritme voor Minimum Spanning Tree . Net als het algoritme van Kruskal is het algoritme van Prim ook a Hebzuchtig algoritme . Dit algoritme begint altijd met een enkel knooppunt en beweegt zich door verschillende aangrenzende knooppunten, om onderweg alle verbonden randen te verkennen.
Het algoritme begint met een lege spanning tree. Het idee is om twee sets hoekpunten te behouden. De eerste set bevat de hoekpunten die al in de MST zijn opgenomen, en de andere set bevat de hoekpunten die nog niet zijn opgenomen. Bij elke stap wordt rekening gehouden met alle randen die de twee sets verbinden en wordt de minimale gewichtsrand van deze randen gekozen. Nadat de rand is gekozen, wordt het andere eindpunt van de rand verplaatst naar de set die MST bevat.
Een groep randen die twee sets hoekpunten in een grafiek met elkaar verbindt, wordt genoemd bezuiniging op de grafentheorie . Zoek dus bij elke stap van het algoritme van Prim een snede, kies de minimale gewichtsrand van de snede en neem dit hoekpunt op in MST Set (de set die reeds opgenomen hoekpunten bevat).
Hoe werkt het algoritme van Prim?
De werking van het algoritme van Prim kan worden beschreven door de volgende stappen te gebruiken:
Stap 1: Bepaal een willekeurig hoekpunt als het startpunt van de MST.
Stap 2: Volg stap 3 tot en met 5 totdat er hoekpunten zijn die niet zijn opgenomen in de MST (bekend als randhoekpunt).
Stap 3: Vind randen die elk boompunt verbinden met de randhoekpunten.
Stap 4: Zoek het minimum tussen deze randen.
Stap 5: Voeg de gekozen rand toe aan de MST als deze geen cyclus vormt.
Stap 6: Breng de MST terug en verlaat de route
Opmerking: Om een cyclus te bepalen, kunnen we de hoekpunten in twee sets verdelen [de ene set bevat de hoekpunten die in MST zijn opgenomen en de andere bevat de randhoekpunten.]
Aanbevolen praktijk Minimale spanningsboom Probeer het!Illustratie van het algoritme van Prim:
Beschouw de volgende grafiek als voorbeeld waarvoor we de Minimum Spanning Tree (MST) moeten vinden.
Voorbeeld van een grafiek
Stap 1: Ten eerste selecteren we een willekeurig hoekpunt dat fungeert als het startpunt van de Minimum Spanning Tree. Hier hebben we een hoekpunt geselecteerd 0 als startpunt.
0 wordt geselecteerd als starthoekpunt
Stap 2: Alle randen die de onvolledige MST en andere hoekpunten verbinden, zijn de randen {0, 1} en {0, 7}. Tussen deze twee is de rand met minimaal gewicht {0, 1}. Neem dus rand en hoekpunt 1 mee in de MST.
1 wordt toegevoegd aan de MST
Stap 3: De randen die de onvolledige MST verbinden met andere hoekpunten zijn {0, 7}, {1, 7} en {1, 2}. Van deze randen is het minimumgewicht 8, dat wil zeggen van de randen {0, 7} en {1, 2}. Laten we hier de rand {0, 7} en het hoekpunt 7 in de MST opnemen. [We hadden ook rand {1, 2} en hoekpunt 2 in de MST kunnen opnemen].
7 wordt toegevoegd in de MST
Stap 4: De randen die de onvolledige MST verbinden met de randhoekpunten zijn {1, 2}, {7, 6} en {7, 8}. Voeg de rand {7, 6} en het hoekpunt 6 toe in de MST omdat deze het minste gewicht heeft (d.w.z. 1).
6 wordt toegevoegd aan de MST
Stap 5: De verbindingsranden zijn nu {7, 8}, {1, 2}, {6, 8} en {6, 5}. Neem rand {6, 5} en hoekpunt 5 op in de MST, aangezien de rand het minimale gewicht (d.w.z. 2) heeft.
Neem hoekpunt 5 op in de MST
Java-subreeksStap 6: Van de huidige verbindingsranden heeft de rand {5, 2} het minimale gewicht. Neem dus die rand en het hoekpunt 2 op in de MST.
Neem hoekpunt 2 op in de MST
Stap 7: De verbindingsranden tussen de onvolledige MST en de andere randen zijn {2, 8}, {2, 3}, {5, 3} en {5, 4}. De rand met het minimale gewicht is rand {2, 8} met gewicht 2. Neem deze rand en het hoekpunt 8 dus op in de MST.
Voeg hoekpunt 8 toe in de MST
Stap 8: Zie hier dat de randen {7, 8} en {2, 3} beide hetzelfde gewicht hebben, wat minimaal is. Maar 7 maakt al deel uit van MST. We zullen dus de rand {2, 3} beschouwen en die rand en hoekpunt 3 opnemen in de MST.
Neem hoekpunt 3 op in MST
Stap 9: Alleen het hoekpunt 4 moet nog worden opgenomen. De minimaal gewogen voorsprong van de onvolledige MST naar 4 is {3, 4}.
Neem hoekpunt 4 op in de MST
De uiteindelijke structuur van de MST is als volgt en het gewicht van de randen van de MST is (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
De structuur van de MST gevormd met behulp van de bovenstaande methode
Opmerking: Als we in de derde stap de rand {1, 2} hadden geselecteerd, zou de MST er als volgt uitzien.
Structuur van de alternatieve MST als we rand {1, 2} in de MST hadden geselecteerd
Hoe het algoritme van Prim implementeren?
Volg de gegeven stappen om de Het algoritme van Prim hierboven vermeld voor het vinden van MST van een grafiek:
- Maak een set mstSet dat de hoekpunten bijhoudt die al in MST zijn opgenomen.
- Wijs een sleutelwaarde toe aan alle hoekpunten in de invoergrafiek. Initialiseer alle sleutelwaarden als INFINITE. Wijs de sleutelwaarde toe als 0 voor het eerste hoekpunt, zodat dit als eerste wordt gekozen.
- Terwijl mstSet omvat niet alle hoekpunten
- Kies een hoekpunt in dat zit er niet in mstSet en heeft een minimale sleutelwaarde.
- Erbij betrekken in in de mstSet .
- Update de sleutelwaarde van alle aangrenzende hoekpunten van in . Om de sleutelwaarden bij te werken, itereert u door alle aangrenzende hoekpunten.
- Voor elk aangrenzend hoekpunt in , als het gewicht van de rand u-v is kleiner dan de vorige sleutelwaarde van in , update de sleutelwaarde als het gewicht van u-v .
Het idee van het gebruik van sleutelwaarden is om de minimale gewichtsrand te kiezen uit de snee . De sleutelwaarden worden alleen gebruikt voor hoekpunten die nog niet zijn opgenomen in MST. De sleutelwaarde voor deze hoekpunten geeft de minimale gewichtsranden aan die ze verbinden met de set hoekpunten die zijn opgenomen in MST.
Hieronder vindt u de implementatie van de aanpak:
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; }> |
>
>
... op Java
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.> |
>
>Uitvoer
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Complexiteitsanalyse van het algoritme van Prim:
Tijdcomplexiteit: O(V2), Als de invoer grafiek wordt weergegeven met behulp van een aangrenzende lijst , dan kan de tijdscomplexiteit van het algoritme van Prim worden teruggebracht tot O(E * logV) met behulp van een binaire heap. Bij deze implementatie overwegen we altijd dat de spanning tree begint bij de wortel van de grafiek
Hulpruimte: O(V)
Andere implementaties van het algoritme van Prim:
Hieronder vindt u enkele andere implementaties van het algoritme van Prim
- Prim's algoritme voor representatie van de aangrenzende matrix – In dit artikel hebben we de methode besproken voor het implementeren van het algoritme van Prim als de grafiek wordt weergegeven door een aangrenzende matrix.
- Prim's algoritme voor weergave van aangrenzende lijsten – In dit artikel wordt de implementatie van het algoritme van Prim beschreven voor grafieken die worden weergegeven door een aangrenzende lijst.
- Prim's algoritme met behulp van Priority Queue: In dit artikel hebben we een tijdefficiënte aanpak besproken om het algoritme van Prim te implementeren.
GEOPTIMALISEERDE AANPAK VAN HET ALGORITME VAN PRIM:
Intuïtie
- We transformeren de aangrenzende matrix in een aangrenzende lijst met behulp van ArrayLijst
. - Vervolgens maken we een Pair-klasse om het hoekpunt en zijn gewicht op te slaan.
- Wij sorteren de lijst op basis van het laagste gewicht.
- We creëren een prioriteitswachtrij en duwen het eerste hoekpunt en zijn gewicht in de wachtrij
- Vervolgens doorlopen we gewoon de randen en slaan we het minste gewicht op in een variabele genaamd jaar.
- Eindelijk geven we na alle hoekpunten de ans terug.
Implementatie
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>> bijvoeglijk naamwoord[V]; // Vul de lijst met aangrenzende randen en hun gewichten voor (int i = 0; i int u = randen[i][0]; int v = randen[i][1]; int wt = randen[i][2 ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt} } // Maak een prioriteitswachtrij om randen op te slaan met hun gewichten prioritaire_wachtrij pq; bezochte array om de bezochte hoekpuntenvector bij te houden |
>
>
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[]>> bijvoeglijk naamwoord = nieuwe Lijstint[]>>(); for (int i = 0; i { adj.Add(nieuwe lijst |
>
>
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>ik) {> >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]; // Gewicht van de randconst u = p[1]; // Vertex verbonden met de rand if (visited[u]) { continue; // Overslaan als het hoekpunt al is bezocht } res += wt; // Voeg het randgewicht toe aan het bezochte resultaat[u] = true; // Markeer het hoekpunt als bezocht // Onderzoek de aangrenzende hoekpunten voor (const v van adj[u]) {/ // v[0] vertegenwoordigt het hoekpunt en v[1] vertegenwoordigt het randgewicht if (!visited[v[0 ]]) { pq.enqueue([v[1], v[0]]); // Voeg de aangrenzende rand toe aan de prioriteitswachtrij } } } return res; // Retourneer de som van de randgewichten van de Minimum Spanning Tree } // Voorbeeld van gebruiksconst-grafiek = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Functieaanroep console.log(spanningTree(3, 3, grafiek));> |
>
javascript trimmen
>Uitvoer
4>
Complexiteitsanalyse van het algoritme van Prim:
Tijdcomplexiteit: O(E*log(E)) waarbij E het aantal randen is
Hulpruimte: O(V^2) waarbij V het aantal hoekpunten is
Prim's algoritme voor het vinden van de minimaal opspannende boom (MST):
Voordelen:
- Het algoritme van Prim vindt gegarandeerd de MST in een verbonden, gewogen grafiek.
- Het heeft een tijdscomplexiteit van O (E log V) met behulp van een binaire heap of Fibonacci-heap, waarbij E het aantal randen is en V het aantal hoekpunten.
- Het is een relatief eenvoudig algoritme om te begrijpen en te implementeren in vergelijking met sommige andere MST-algoritmen.
Nadelen:
- Net als het algoritme van Kruskal kan het algoritme van Prim traag zijn bij compacte grafieken met veel randen, omdat het minstens één keer over alle randen moet worden herhaald.
- Het algoritme van Prim is afhankelijk van een prioriteitswachtrij, die extra geheugen in beslag kan nemen en het algoritme bij zeer grote grafieken kan vertragen.
- De keuze van het startknooppunt kan de MST-uitvoer beïnvloeden, wat in sommige toepassingen mogelijk niet wenselijk is.