Introducere în algoritmul lui Prim:
Am discutat Algoritmul lui Kruskal pentru Minimum Spanning Tree . La fel ca algoritmul lui Kruskal, algoritmul lui Prim este, de asemenea, a Algoritm lacom . Acest algoritm începe întotdeauna cu un singur nod și se deplasează prin mai multe noduri adiacente, pentru a explora toate marginile conectate pe parcurs.
Algoritmul începe cu un arbore de acoperire gol. Ideea este de a menține două seturi de vârfuri. Primul set conține nodurile deja incluse în MST, iar celălalt set conține nodurile care nu sunt încă incluse. La fiecare pas, ia în considerare toate marginile care leagă cele două seturi și alege marginea de greutate minimă din aceste margini. După alegerea muchiei, se mută celălalt punct final al muchiei către setul care conține MST.
Se numește un grup de muchii care conectează două seturi de vârfuri într-un grafic decupat în teoria grafurilor . Deci, la fiecare pas al algoritmului lui Prim, găsiți o tăietură, alegeți marginea greutății minime din tăietură și includeți acest vârf în MST Set (setul care conține deja vârfuri incluse).
Cum funcționează algoritmul lui Prim?
Funcționarea algoritmului lui Prim poate fi descrisă folosind următorii pași:
Pasul 1: Determinați un vârf arbitrar ca vârf de început al MST.
Pasul 2: Urmați pașii de la 3 la 5 până când există vârfuri care nu sunt incluse în MST (cunoscut sub numele de vârf marginal).
Pasul 3: Găsiți muchiile care conectează orice vârf de arbore cu vârfurile marginale.
Pasul 4: Găsiți minimul dintre aceste margini.
Pasul 5: Adăugați marginea aleasă la MST dacă nu formează niciun ciclu.
Pasul 6: Întoarceți MST-ul și ieșiți
Notă: Pentru a determina un ciclu, putem împărți nodurile în două seturi [un set conține vârfurile incluse în MST, iar celălalt conține vârfurile marginale.]
Practică recomandată Arborele de întindere minimă Încercați!Ilustrație a algoritmului lui Prim:
Luați în considerare următorul grafic ca exemplu pentru care trebuie să găsim arborele de întindere minim (MST).
Exemplu de grafic
Pasul 1: În primul rând, selectăm un vârf arbitrar care acționează ca vârful de pornire al arborelui de întindere minimă. Aici am selectat vârful 0 ca vârf de pornire.
0 este selectat ca vârf de pornire
Pasul 2: Toate muchiile care conectează MST incomplet și alte vârfuri sunt muchiile {0, 1} și {0, 7}. Între acestea două muchia cu greutate minimă este {0, 1}. Deci includeți muchia și vârful 1 în MST.
1 este adăugat la MST
Pasul 3: Muchiile care conectează MST-ul incomplet la alte vârfuri sunt {0, 7}, {1, 7} și {1, 2}. Printre aceste muchii greutatea minimă este 8 care este a muchiilor {0, 7} și {1, 2}. Să includem aici muchia {0, 7} și vârful 7 în MST. [Am fi putut include, de asemenea, muchia {1, 2} și vârful 2 în MST].
7 este adăugat în MST
Pasul 4: Muchiile care conectează MST-ul incomplet cu vârfurile marginale sunt {1, 2}, {7, 6} și {7, 8}. Adăugați muchia {7, 6} și vârful 6 în MST, deoarece are cea mai mică greutate (adică, 1).
6 este adăugat în MST
Pasul 5: Muchiile de legătură sunt acum {7, 8}, {1, 2}, {6, 8} și {6, 5}. Includeți muchia {6, 5} și vârful 5 în MST, deoarece muchia are greutatea minimă (adică, 2) între ele.
Includeți vârful 5 în MST
Pasul 6: Dintre muchiile de legătură curente, muchia {5, 2} are greutatea minimă. Deci includeți acea margine și vârful 2 în MST.
Includeți vârful 2 în MST
Pasul 7: Muchiile de legătură dintre MST incomplet și celelalte muchii sunt {2, 8}, {2, 3}, {5, 3} și {5, 4}. Muchia cu greutate minimă este muchia {2, 8} care are greutatea 2. Deci includeți această muchie și vârful 8 în MST.
Adăugați vârful 8 în MST
Pasul 8: Vedeți aici că muchiile {7, 8} și {2, 3} au ambele aceeași greutate, care sunt minime. Dar 7 face deja parte din MST. Deci vom lua în considerare muchia {2, 3} și vom include acea muchie și vârful 3 în MST.
Includeți vârful 3 în MST
Pasul 9: Doar vârful 4 rămâne de inclus. Marginea minimă ponderată de la MST incomplet la 4 este {3, 4}.
Includeți vârful 4 în MST
Structura finală a MST-ului este următoarea, iar greutatea marginilor MST-ului este (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
Structura MST-ului s-a format folosind metoda de mai sus
Notă: Dacă am fi selectat muchia {1, 2} în al treilea pas, atunci MST-ul ar arăta ca următorul.
Structura MST-ului alternativ dacă am fi selectat muchia {1, 2} în MST
Cum se implementează algoritmul lui Prim?
Urmați pașii dați pentru a utiliza Algoritmul lui Prim menționat mai sus pentru găsirea MST al unui grafic:
- Creați un set mstSet care ține evidența nodurilor deja incluse în MST.
- Atribuiți o valoare cheie tuturor nodurilor din graficul de intrare. Inițializați toate valorile cheie ca INFINITE. Atribuiți valoarea cheii ca 0 pentru primul vârf, astfel încât acesta să fie ales primul.
- In timp ce mstSet nu include toate nodurile
- Alegeți un vârf în asta nu este acolo in mstSet și are o valoare minimă a cheii.
- Include în în mstSet .
- Actualizați valoarea cheie a tuturor nodurilor adiacente ale în . Pentru a actualiza valorile cheii, iterați prin toate vârfurile adiacente.
- Pentru fiecare vârf adiacent în , dacă greutatea marginii u-v este mai mică decât valoarea cheie anterioară a în , actualizați valoarea cheii ca greutate a u-v .
Ideea utilizării valorilor cheie este de a alege marginea minimă de greutate din a tăia . Valorile cheie sunt folosite numai pentru nodurile care nu sunt încă incluse în MST, valoarea cheie pentru aceste vârfuri indică marginile minime de greutate care le conectează la setul de vârfuri incluse în MST.
Mai jos este implementarea abordării:
C++
aleator fără generator în java
// 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> |
>
>
program prime în java
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]>>>> mstSet[v]>=>=> False> > >and> key[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.> |
>
>Ieșire
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Analiza complexității algoritmului lui Prim:
Complexitatea timpului: O(V2), Dacă intrarea graficul este reprezentat folosind o listă de adiacență , atunci complexitatea temporală a algoritmului lui Prim poate fi redusă la O(E * logV) cu ajutorul unui heap binar. În această implementare, luăm în considerare întotdeauna ca arborele de întindere să înceapă de la rădăcina graficului
Spațiu auxiliar: O(V)
Alte implementări ale algoritmului lui Prim:
Mai jos sunt prezentate câteva alte implementări ale algoritmului Prim
- Algoritmul lui Prim pentru reprezentarea matricei de adiacență – În acest articol am discutat despre metoda de implementare a algoritmului lui Prim dacă graficul este reprezentat printr-o matrice de adiacență.
- Algoritmul lui Prim pentru reprezentarea listei de adiacență – În acest articol, implementarea algoritmului lui Prim este descrisă pentru graficele reprezentate printr-o listă de adiacență.
- Algoritmul lui Prim folosind Coada de Prioritate: În acest articol, am discutat despre o abordare eficientă în timp pentru a implementa algoritmul lui Prim.
ABORDAREA OPTIMIZATĂ A ALGORITMULUI PRIM:
Intuiţie
- Transformăm matricea de adiacență în listă de adiacență folosind ArrayList
. - Apoi creăm o clasă Pair pentru a stoca vârful și greutatea acestuia.
- Sortăm lista în funcție de greutatea cea mai mică.
- Creăm o coadă de prioritate și împingem primul vârf și greutatea acestuia în coadă
- Apoi parcurgem marginile sale și stocăm cea mai mică greutate într-o variabilă numită ani.
- În cele din urmă, după tot vârful, întoarcem ans.
Implementarea
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]; // Completați lista de adiacențe cu muchii și greutățile lor pentru (int i = 0; i int u = muchii[i][0]; int v = muchii[i][1]; int wt = muchii[i][2] ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); matrice vizitată pentru a ține evidența vectorului nodurilor vizitate |
>
>
Java
coadă și coadă de prioritate în 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
metode arraylist
import> heapq> def> tree(V, E, edges):> ># Create an adjacency list representation of the graph> >adj>=> [[]>for> _>in> range>(V)]> ># Fill the adjacency list with edges and their weights> >for> i>in> range>(E):> >u, v, wt>=> edges[i]> >adj[u].append((v, wt))> >adj[v].append((u, wt))> ># Create a priority queue to store edges with their weights> >pq>=> []> ># Create a visited array to keep track of visited vertices> >visited>=> [>False>]>*> V> ># Variable to store the result (sum of edge weights)> >res>=> 0> ># Start with vertex 0> >heapq.heappush(pq, (>0>,>0>))> ># Perform Prim's algorithm to find the Minimum Spanning Tree> >while> pq:> >wt, u>=> heapq.heappop(pq)> >if> visited[u]:> >continue> ># Skip if the vertex is already visited> >res>+>=> wt> ># Add the edge weight to the result> >visited[u]>=> True> ># Mark the vertex as visited> ># Explore the adjacent vertices> >for> v, weight>in> adj[u]:> >if> not> visited[v]:> >heapq.heappush(pq, (weight, v))> ># Add the adjacent edge to the priority queue> >return> res> ># Return the sum of edge weights of the Minimum Spanning Tree> if> __name__>=>=> '__main__'>:> >graph>=> [[>0>,>1>,>5>],> >[>1>,>2>,>3>],> >[>0>,>2>,>1>]]> ># Function call> >print>(tree(>3>,>3>, graph))> |
>
>
C#
using> System;> using> System.Collections.Generic;> public> class> MinimumSpanningTree> {> >// Function to find sum of weights of edges of the Minimum Spanning Tree.> >public> static> int> SpanningTree(>int> V,>int> E,>int>[,] edges)> >{> >// Create an adjacency list representation of the graph> >Listint[]>> adj = nou Listint[]>>(); pentru (int i = 0; i { adj.Add(listă nouă |
>
>
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]; // Greutatea muchiei const u = p[1]; // Vârf conectat la margine if (visited[u]) { continue; // Omite dacă vârful este deja vizitat } res += wt; // Adăugați greutatea marginii la rezultatul vizitat[u] = true; // Marcați vârful ca vizitat // Explorați vârfurile adiacente pentru (const v of adj[u]) { // v[0] reprezintă vârful și v[1] reprezintă greutatea muchiei dacă (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Adăugați marginea adiacentă la coada de prioritate } } } return res; // Întoarce suma greutăților marginilor arborelui de întindere minim } // Exemplu de grafic const de utilizare = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Apel de funcție console.log(spanningTree(3, 3, graph));>>> |
>4>
Analiza complexității algoritmului lui Prim:
Complexitatea timpului: O(E*log(E)) unde E este numărul de muchii
Spațiu auxiliar: O(V^2) unde V este numărul vârfurilor
Algoritmul lui Prim pentru găsirea arborelui de acoperire minim (MST):
Avantaje:
- Algoritmul lui Prim este garantat să găsească MST-ul într-un grafic conectat, ponderat.
- Are o complexitate de timp de O(E log V) folosind un heap binar sau Fibonacci, unde E este numărul de muchii și V este numărul de vârfuri.
- Este un algoritm relativ simplu de înțeles și implementat în comparație cu alți algoritmi MST.
Dezavantaje:
- La fel ca algoritmul lui Kruskal, algoritmul lui Prim poate fi lent pe grafice dense cu multe muchii, deoarece necesită iterarea peste toate muchiile cel puțin o dată.
- Algoritmul lui Prim se bazează pe o coadă de prioritate, care poate ocupa memorie suplimentară și poate încetini algoritmul pe grafice foarte mari.
- Alegerea nodului de pornire poate afecta ieșirea MST, ceea ce poate să nu fie de dorit în unele aplicații.