Ievads Prim algoritmā:
Mēs esam apsprieduši Kruskal algoritms minimālajam stiepšanās kokam . Tāpat kā Kruskal algoritms, arī Prima algoritms ir a Mantkārīgs algoritms . Šis algoritms vienmēr sākas ar vienu mezglu un pārvietojas pa vairākiem blakus esošajiem mezgliem, lai pa ceļam izpētītu visas savienotās malas.
Algoritms sākas ar tukšu aptverošo koku. Ideja ir saglabāt divas virsotņu kopas. Pirmajā kopā ir virsotnes, kas jau ir iekļautas MST, un otrā kopā ir virsotnes, kas vēl nav iekļautas. Katrā solī tas ņem vērā visas malas, kas savieno abus komplektus, un no šīm malām izvēlas minimālo svara malu. Pēc malas izvēles tas pārvieto otru malas gala punktu uz kopu, kurā ir MST.
Tiek saukta malu grupa, kas savieno divas virsotņu kopas grafā izgriezt grafu teorijā . Tātad katrā Prim algoritma solī atrodiet griezumu, izvēlieties griezuma minimālo svara malu un iekļaujiet šo virsotni MST komplektā (kopā, kas satur jau iekļautās virsotnes).
Kā darbojas Prim algoritms?
Prim algoritma darbību var aprakstīt, izmantojot šādas darbības:
1. darbība: Nosakiet patvaļīgu virsotni kā MST sākuma virsotni.
2. darbība: Veiciet 3.–5. darbību, līdz ir virsotnes, kas nav iekļautas MST (pazīstamas kā fringe vertex).
3. darbība: Atrodiet malas, kas savieno jebkuru koka virsotni ar bārkstiņu virsotnēm.
4. darbība: Atrodiet minimumu starp šīm malām.
5. darbība: Pievienojiet izvēlēto malu MST, ja tā neveido nekādu ciklu.
6. darbība: Atgriezieties MST un izejiet
Piezīme: Cikla noteikšanai mēs varam sadalīt virsotnes divās kopās [vienā kopā ir MST ietvertās virsotnes, bet otrā - bārkstiņu virsotnes.]
Ieteicamā prakse Minimālais aptverošais koks Izmēģiniet to!Prima algoritma ilustrācija:
Apsveriet šo grafiku kā piemēru, kuram mums jāatrod minimālais aptverošais koks (MST).
Grafika piemērs
1. darbība: Pirmkārt, mēs izvēlamies patvaļīgu virsotni, kas darbojas kā minimālā stiepuma koka sākuma virsotne. Šeit mēs esam izvēlējušies virsotni 0 kā sākuma virsotne.
0 ir izvēlēta kā sākuma virsotne
2. darbība: Visas malas, kas savieno nepabeigto MST un citas virsotnes, ir malas {0, 1} un {0, 7}. Starp šiem diviem mala ar minimālo svaru ir {0, 1}. Tāpēc iekļaujiet malu un virsotni 1 MST.
1 tiek pievienots MST
3. darbība: Malas, kas savieno nepabeigto MST ar citām virsotnēm, ir {0, 7}, {1, 7} un {1, 2}. Starp šīm malām minimālais svars ir 8, kas ir no malām {0, 7} un {1, 2}. Šeit iekļaujam MST malu {0, 7} un virsotni 7. [MST varējām iekļaut arī malu {1, 2} un virsotni 2].
7 ir pievienots MST
4. darbība: Malas, kas savieno nepilnīgo MST ar bārkstiņu virsotnēm, ir {1, 2}, {7, 6} un {7, 8}. Pievienojiet malu {7, 6} un virsotni 6 MST, jo tai ir vismazākais svars (t.i., 1).
6 ir pievienots MST
5. darbība: Tagad savienojošās malas ir {7, 8}, {1, 2}, {6, 8} un {6, 5}. MST iekļaujiet malu {6, 5} un virsotni 5, jo malai ir minimālais svars (t.i., 2).
MST iekļaujiet virsotni 5
6. darbība: No pašreizējām savienojošām malām malai {5, 2} ir minimālais svars. Tāpēc iekļaujiet šo malu un virsotni 2 MST.
Iekļaut 2. virsotni MST
7. darbība: Savienojošās malas starp nepabeigto MST un pārējām malām ir {2, 8}, {2, 3}, {5, 3} un {5, 4}. Mala ar minimālo svaru ir mala {2, 8}, kuras svars ir 2. Tāpēc iekļaujiet šo malu un virsotni 8 MST.
Pievienojiet virsotni 8 MST
8. darbība: Skatiet šeit, ka malām {7, 8} un {2, 3} ir vienāds svars, kas ir minimālais. Bet 7 jau ir daļa no MST. Tāpēc mēs apsvērsim malu {2, 3} un iekļausim šo malu un virsotni 3 MST.
Iekļaut 3. virsotni MST
9. darbība: Atliek iekļaut tikai virsotni 4. Minimālā svērtā mala no nepabeigtā MST līdz 4 ir {3, 4}.
Iekļaut 4. virsotni MST
MST galīgā struktūra ir šāda, un MST malu svars ir (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
MST struktūra izveidota, izmantojot iepriekš minēto metodi
Piezīme: Ja mēs trešajā darbībā būtu atlasījuši malu {1, 2}, tad MST izskatītos šādi.
Alternatīvās MST struktūra, ja MST būtu atlasījuši malu {1, 2}
Kā ieviest Prim algoritmu?
Izpildiet norādītās darbības, lai izmantotu Prima algoritms minēts iepriekš, lai atrastu diagrammas MST:
- Izveidojiet komplektu mstSet kas seko virsotnēm, kas jau ir iekļautas MST.
- Piešķiriet atslēgas vērtību visām virsotnēm ievades diagrammā. Inicializējiet visas galvenās vērtības kā INFINITE. Piešķiriet atslēgas vērtību 0 pirmajai virsotnei, lai tā tiktu izvēlēta pirmā.
- Kamēr mstSet neietver visas virsotnes
- Izvēlieties virsotni iekšā kas tur nav iekšā mstSet un tam ir minimālā atslēgas vērtība.
- Iekļaut iekšā iekš mstSet .
- Atjauniniet visu blakus esošo virsotņu atslēgas vērtību iekšā . Lai atjauninātu atslēgas vērtības, atkārtojiet visas blakus esošās virsotnes.
- Katrai blakus virsotnei iekšā , ja malas svars u-v ir mazāka par iepriekšējo atslēgas vērtību iekšā , atjauniniet atslēgas vērtību kā svaru u-v .
Galveno vērtību izmantošanas ideja ir izvēlēties minimālo svara malu no griezt . Atslēgas vērtības tiek izmantotas tikai virsotnēm, kas vēl nav iekļautas MST, šo virsotņu atslēgas vērtība norāda minimālās svara malas, kas tās savieno ar MST iekļauto virsotņu kopu.
Tālāk ir aprakstīta pieejas īstenošana:
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]>>> 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.> |
>
>Izvade
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Prima algoritma sarežģītības analīze:
Laika sarežģītība: O(V2), Ja ievade grafiks tiek attēlots, izmantojot blakus esošo sarakstu , tad Prim algoritma laika sarežģītību ar binārās kaudzes palīdzību var samazināt līdz O(E * logV). Šajā īstenošanā mēs vienmēr apsveram, ka aptverošais koks sākas no diagrammas saknes
Palīgtelpa: O(V)
Citas Prim algoritma ieviešanas iespējas:
Tālāk ir sniegti daži citi Prim algoritma varianti
- Prima algoritms blakusesības matricas attēlošanai - Šajā rakstā mēs esam apsprieduši Prim algoritma ieviešanas metodi, ja grafu attēlo blakusesības matrica.
- Prima algoritms blakus esošo sarakstu attēlošanai – Šajā rakstā Prim algoritma ieviešana ir aprakstīta grafikiem, kas attēloti ar blakus esošo sarakstu.
- Prim algoritms, izmantojot prioritāro rindu: Šajā rakstā mēs esam apsprieduši laiku efektīvu pieeju Prim algoritma ieviešanai.
PRIM ALGORITMA OPTIMIZĒTA PIEEJA:
Intuīcija
- Mēs pārveidojam blakusesību matricu par blakus esošo sarakstu, izmantojot ArrayList
. - Tad mēs izveidojam Pair klasi, lai saglabātu virsotni un tās svaru.
- Mēs sakārtojam sarakstu pēc mazākā svara.
- Mēs izveidojam prioritāro rindu un iespiežam rindā pirmo virsotni un tās svaru
- Tad mēs vienkārši šķērsojam tā malas un saglabājam mazāko svaru mainīgajā, ko sauc gadiem.
- Beidzot pēc visas virsotnes mēs atgriežam ans.
Īstenošana
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]; // Aizpildiet blakus esošo sarakstu ar malām un to svariem (int i = 0; i int u = malas[i][0]; int v = malas[i][1]; int wt = malas[i][2 ]; adj[u].push_back({v, wt}). apmeklētais masīvs, lai izsekotu apmeklēto virsotņu vektoram |
>
>
operētājsistēma
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 = jauns saraksts[]>>(); for (int i = 0; i { adj.Add(new List |
>
>
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]; // Malas svars const u = p[1]; // Virsotne, kas savienota ar malu if (apmeklēta[u]) { turpināt; // Izlaist, ja virsotne jau ir apmeklēta } res += wt; // Apmeklētajam rezultātam pievienojiet malas svaru [u] = true; // Atzīmēt virsotni kā apmeklētu // Izpētīt blakus esošās virsotnes priekš (const v of adj[u]) { // v[0] apzīmē virsotni un v[1] apzīmē malas svaru, ja (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Pievienot prioritārajai rindai blakus esošo malu } } } return res; // Atgriezt minimālā aptverošā koka malu svaru summu } // Piemēra lietojums const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Funkcijas izsaukums console.log(spanningTree(3, 3, graph));>> |
>4>
Prima algoritma sarežģītības analīze:
Laika sarežģītība: O(E*log(E)), kur E ir malu skaits
Palīgtelpa: O(V^2), kur V ir virsotnes skaits
Prim algoritms minimālā aptverošā koka (MST) atrašanai:
Priekšrocības:
- Prim algoritms tiek garantēts, lai atrastu MST savienotā, svērtā grafikā.
- Tam ir laika sarežģītība O(E log V), izmantojot bināro kaudzi vai Fibonači kaudzi, kur E ir šķautņu skaits un V ir virsotņu skaits.
- Salīdzinot ar dažiem citiem MST algoritmiem, tas ir salīdzinoši vienkāršs izprotams un ieviešams algoritms.
Trūkumi:
- Tāpat kā Kruskal algoritms, Prim algoritms var būt lēns blīvos grafikos ar daudzām malām, jo tas prasa vismaz vienu reizi atkārtot visas malas.
- Prim algoritms balstās uz prioritāro rindu, kas var aizņemt papildu atmiņu un palēnināt algoritmu ļoti lielos grafikos.
- Sākuma mezgla izvēle var ietekmēt MST izvadi, kas dažās lietojumprogrammās var nebūt vēlama.