Uvod v Primov algoritem:
Razpravljali smo Kruskalov algoritem za minimalno vpeto drevo . Tako kot Kruskalov algoritem je tudi Primov algoritem a Požrešen algoritem . Ta algoritem se vedno začne z enim vozliščem in se premika skozi več sosednjih vozlišč, da razišče vse povezane robove na poti.
Algoritem se začne s praznim vpetim drevesom. Ideja je ohraniti dva niza vozlišč. Prvi niz vsebuje vozlišča, ki so že vključena v MST, drugi niz pa vsebuje vozlišča, ki še niso vključena. Na vsakem koraku upošteva vse robove, ki povezujejo dva niza, in iz teh robov izbere rob najmanjše teže. Po izbiri roba premakne drugo končno točko roba v niz, ki vsebuje MST.
Imenuje se skupina robov, ki povezuje dva niza vozlišč v grafu cut v teoriji grafov . Torej, na vsakem koraku Primovega algoritma poiščite rez, izberite rob z najmanjšo težo iz reza in vključite to točko v MST Set (množica, ki vsebuje že vključena oglišča).
Kako deluje Primov algoritem?
Delovanje Primovega algoritma je mogoče opisati z naslednjimi koraki:
Korak 1: Določite poljubno točko kot začetno točko MST.
2. korak: Sledite korakom od 3 do 5, dokler ne obstajajo oglišča, ki niso vključena v MST (znana kot obrobna oglišča).
3. korak: Poiščite robove, ki povezujejo poljubno oglišče drevesa z obrobnimi oglišči.
4. korak: Poiščite minimum med temi robovi.
5. korak: Dodajte izbrani rob v MST, če ne tvori nobenega cikla.
6. korak: Vrnite MST in izstopite
Opomba: Za določitev cikla lahko razdelimo oglišča v dva niza [en niz vsebuje oglišča, vključena v MST, drugi pa vsebuje obrobna oglišča.]
Priporočena praksa Najmanjše vpeto drevo Poskusite!Ilustracija Primovega algoritma:
Upoštevajte naslednji graf kot primer, za katerega moramo najti minimalno vpeto drevo (MST).
Primer grafa
Korak 1: Najprej izberemo poljubno oglišče, ki deluje kot začetno oglišče minimalnega vpetega drevesa. Tukaj smo izbrali točko 0 kot začetno točko.
0 je izbrana kot začetna točka
2. korak: Vsi robovi, ki povezujejo nepopolno MST in druga oglišča, so robovi {0, 1} in {0, 7}. Med tema dvema je rob z najmanjšo težo {0, 1}. Torej vključite rob in točko 1 v MST.
1 se doda v MST
3. korak: Robovi, ki povezujejo nepopolni MST z drugimi vozlišči, so {0, 7}, {1, 7} in {1, 2}. Med temi robovi je najmanjša utež 8, kar je robov {0, 7} in {1, 2}. Tu vključimo rob {0, 7} in oglišče 7 v MST. [Lahko bi vključili tudi rob {1, 2} in točko 2 v MST].
7 je dodan v MST
4. korak: Robovi, ki povezujejo nepopolni MST z robovi, so {1, 2}, {7, 6} in {7, 8}. Dodajte rob {7, 6} in oglišče 6 v MST, saj ima najmanjšo težo (tj. 1).
6 je dodan v MST
5. korak: Povezovalni robovi so zdaj {7, 8}, {1, 2}, {6, 8} in {6, 5}. Vključite rob {6, 5} in točko 5 v MST, saj ima rob najmanjšo težo (tj. 2) med njimi.
Vključi točko 5 v MST
6. korak: Med trenutnimi povezovalnimi robovi ima rob {5, 2} najmanjšo težo. Torej vključi ta rob in točko 2 v MST.
Vključite točko 2 v MST
7. korak: Povezovalni robovi med nepopolnim MST in drugimi robovi so {2, 8}, {2, 3}, {5, 3} in {5, 4}. Rob z najmanjšo težo je rob {2, 8}, ki ima težo 2. Torej vključite ta rob in oglišče 8 v MST.
Dodajte točko 8 v MST
8. korak: Tukaj vidite, da imata robovi {7, 8} in {2, 3} enako težo, ki sta minimalni. Toda 7 je že del MST. Zato bomo upoštevali rob {2, 3} in ta rob in točko 3 vključili v MST.
Vključite točko 3 v MST
9. korak: Vključiti je treba le še točko 4. Najmanjši uteženi rob od nepopolnega MST do 4 je {3, 4}.
V MST vključi točko 4
Končna struktura MST je naslednja, teža robov MST pa je (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
Struktura MST oblikovana z uporabo zgornje metode
Opomba: Če bi v tretjem koraku izbrali rob {1, 2}, bi MST izgledal takole.
Struktura nadomestnega MST, če smo izbrali rob {1, 2} v MST
Kako implementirati Primov algoritem?
Za uporabo sledite danim korakom Primov algoritem omenjeno zgoraj za iskanje MST grafa:
- Ustvari komplet mstSet ki spremlja vozlišča, ki so že vključena v MST.
- Vsem vozliščem v vhodnem grafu dodelite ključno vrednost. Inicializirajte vse ključne vrednosti kot NESKONČNE. Dodelite vrednost ključa kot 0 za prvo točko, tako da bo izbrana prva.
- Medtem mstSet ne vključuje vseh vozlišč
- Izberite vrh v tega ni v mstSet in ima minimalno ključno vrednost.
- Vključi v v mstSet .
- Posodobite vrednost ključa vseh sosednjih točk v . Če želite posodobiti ključne vrednosti, ponovite skozi vsa sosednja vozlišča.
- Za vsako sosednjo točko v , če je teža roba u-v je manjša od prejšnje ključne vrednosti v , posodobi ključno vrednost kot težo u-v .
Zamisel uporabe ključnih vrednosti je izbira najmanjše teže med rezati . Vrednosti ključa se uporabljajo samo za vozlišča, ki še niso vključena v MST, vrednost ključa za ta vozlišča označuje robove najmanjše teže, ki jih povezujejo z nizom vozlišč, vključenih v MST.
Spodaj je izvedba pristopa:
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> |
>
>
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.> |
>
>Izhod
logika prenosa registra
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Analiza kompleksnosti Primovega algoritma:
Časovna zapletenost: O(V2), če je vnos graf je predstavljen s seznamom sosednosti , potem lahko časovno kompleksnost Primovega algoritma zmanjšamo na O(E * logV) s pomočjo binarne kopice. Pri tej izvedbi vedno upoštevamo, da se vpeto drevo začne pri korenu grafa
Pomožni prostor: O(V)
Druge izvedbe Primovega algoritma:
Spodaj je navedenih nekaj drugih izvedb Primovega algoritma
- Primov algoritem za predstavitev matrike sosednosti – V tem članku smo razpravljali o metodi implementacije Primovega algoritma, če je graf predstavljen z matriko sosednosti.
- Primov algoritem za predstavitev seznama sosednosti – V tem članku je opisana implementacija Primovega algoritma za grafe, ki jih predstavlja seznam sosednosti.
- Primov algoritem z uporabo prednostne čakalne vrste: V tem članku smo razpravljali o časovno učinkovitem pristopu za implementacijo Primovega algoritma.
OPTIMIZIRAN PRISTOP PRIMOVEGA ALGORITMA:
Intuicija
- Matriko sosednosti pretvorimo v seznam sosednosti z uporabo ArrayList
. - Nato ustvarimo razred Pair za shranjevanje vozlišča in njegove teže.
- Seznam razvrstimo na podlagi najmanjše teže.
- Ustvarimo prednostno čakalno vrsto in v čakalno vrsto potisnemo prvo točko in njeno težo
- Nato samo prečkamo njene robove in shranimo najmanjšo težo v spremenljivko, imenovano leta.
- Končno po vseh točkah vrnemo ans.
Izvedba
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]; // Izpolnite seznam sosednosti z robovi in njihovimi utežmi za (int i = 0; i int u = robovi[i][0]; int v = robovi[i][1]; int wt = robovi[i][2) ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); // Ustvari prednostno čakalno vrsto z njihovimi utežmi priority_queue pq; obiskano polje za sledenje vektorju obiskanih vozlišč |
>
>
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 = nov Listint[]>>(); for (int i = 0; i { adj.Add(nov seznam |
>
>
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]; // Teža roba const u = p[1]; // Vozlišče povezano z robom if (obiskano[u]) { continue; // Preskoči, če je vozlišče že obiskano } res += wt; // Dodajte težo roba rezultatu visited[u] = true; // Označi vozlišče kot obiskano // Raziščite sosednja oglišča za (const v of adj[u]) { // v[0] predstavlja oglišče in v[1] predstavlja težo roba, če (!visited[v[0) ]]) { pq.enqueue([v[1], v[0]]); // Dodajanje sosednjega roba v prednostno čakalno vrsto } } } return res; // Vrni vsoto uteži robov najmanjšega vpetega drevesa } // Primer uporabe const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Klic funkcije console.log(spanningTree(3, 3, graph));> |
>
>Izhod
4>
Analiza kompleksnosti Primovega algoritma:
Časovna zapletenost: O(E*log(E)), kjer je E število robov
Pomožni prostor: O(V^2), kjer je V številka oglišča
Primov algoritem za iskanje minimalnega vpetega drevesa (MST):
Prednosti:
- Primov algoritem zajamčeno najde MST v povezanem, tehtanem grafu.
- Ima časovno kompleksnost O(E log V) z uporabo binarne kopice ali Fibonaccijeve kopice, kjer je E število robov in V število vozlišč.
- V primerjavi z nekaterimi drugimi algoritmi MST je razmeroma preprost algoritem za razumevanje in implementacijo.
Slabosti:
- Tako kot Kruskalov algoritem je lahko Primov algoritem počasen na gostih grafih z veliko robovi, saj zahteva ponavljanje čez vse robove vsaj enkrat.
- Primov algoritem se opira na prednostno čakalno vrsto, ki lahko zavzame dodaten pomnilnik in upočasni algoritem na zelo velikih grafih.
- Izbira začetnega vozlišča lahko vpliva na izhod MST, kar v nekaterih aplikacijah morda ni zaželeno.