Prim algoritmo įvadas:
Mes aptarėme Kruskal algoritmas minimaliam besitęsiančiam medžiui . Kaip ir Kruskal algoritmas, Primo algoritmas taip pat yra a Godus algoritmas . Šis algoritmas visada prasideda nuo vieno mazgo ir juda per kelis gretimus mazgus, kad pakeliui ištirtų visus sujungtus kraštus.
Algoritmas prasideda tuščiu apimančiu medžiu. Idėja yra išlaikyti du viršūnių rinkinius. Pirmajame rinkinyje yra viršūnės, jau įtrauktos į MST, o kitame rinkinyje yra viršūnės, kurios dar neįtrauktos. Kiekviename žingsnyje atsižvelgiama į visus kraštus, jungiančius du rinkinius, ir iš šių kraštų parenka mažiausią svorio kraštą. Pasirinkęs kraštą, kitas krašto galinis taškas perkeliamas į rinkinį, kuriame yra MST.
Vadinama briaunų grupė, jungianti dvi grafo viršūnių aibes iškirpti grafų teorijoje . Taigi, kiekviename Prim algoritmo žingsnyje raskite pjūvį, iš pjūvio pasirinkite minimalų svorio kraštą ir įtraukite šią viršūnę į MST rinkinį (aibinį, kuriame jau yra įtrauktos viršūnės).
Kaip veikia Prim algoritmas?
Prim algoritmo veikimą galima apibūdinti atliekant šiuos veiksmus:
1 žingsnis: Nustatykite savavališką viršūnę kaip pradinę MST viršūnę.
2 žingsnis: Atlikite 3–5 veiksmus, kol atsiras viršūnių, kurios neįtrauktos į MST (žinoma kaip pakraščio viršūnė).
3 veiksmas: Raskite briaunas, jungiančias bet kurią medžio viršūnę su pakraščio viršūnėmis.
4 veiksmas: Raskite minimumą tarp šių kraštų.
5 veiksmas: Pridėkite pasirinktą kraštą prie MST, jei jis nesudaro jokio ciklo.
6 veiksmas: Grąžinkite MST ir išeikite
Pastaba: Norėdami nustatyti ciklą, viršūnes galime padalyti į dvi aibes [viename rinkinyje yra viršūnės, įtrauktos į MST, o kitame yra pakraščių viršūnės.]
Rekomenduojamas minimalus besitęsiantis medis Išbandykite!Primo algoritmo iliustracija:
Apsvarstykite toliau pateiktą grafiką kaip pavyzdį, kuriam reikia rasti minimalų aprėpties medį (MST).
Grafo pavyzdys
1 žingsnis: Pirmiausia pasirenkame savavališką viršūnę, kuri veikia kaip pradinė minimalaus aprėpimo medžio viršūnė. Čia pasirinkome viršūnę 0 kaip pradinė viršūnė.
0 pasirinkta kaip pradinė viršūnė
2 žingsnis: Visos briaunos, jungiančios nebaigtą MST ir kitas viršūnes, yra briaunos {0, 1} ir {0, 7}. Tarp šių dviejų kraštinė su minimaliu svoriu yra {0, 1}. Taigi į MST įtraukite kraštą ir viršūnę 1.
1 pridedamas prie MST
3 veiksmas: Neužbaigtą MST su kitomis viršūnėmis jungiančios briaunos yra {0, 7}, {1, 7} ir {1, 2}. Tarp šių kraštų mažiausias svoris yra 8, tai yra kraštų {0, 7} ir {1, 2}. Įtraukime kraštą {0, 7} ir viršūnę 7 į MST. [Taip pat galėjome įtraukti kraštą {1, 2} ir viršūnę 2 į MST].
7 įtrauktas į MST
4 veiksmas: Briaunos, jungiančios neužbaigtą MST su pakraščio viršūnėmis, yra {1, 2}, {7, 6} ir {7, 8}. Pridėkite kraštą {7, 6} ir viršūnę 6 MST, nes ji turi mažiausią svorį (t. y. 1).
6 įtrauktas į MST
5 veiksmas: Dabar jungiamosios briaunos yra {7, 8}, {1, 2}, {6, 8} ir {6, 5}. Į MST įtraukite kraštą {6, 5} ir 5 viršūnę, nes briauna turi mažiausią svorį (t. y. 2).
Į MST įtraukite 5 viršūnę
6 veiksmas: Tarp dabartinių jungiamųjų kraštų kraštas {5, 2} turi mažiausią svorį. Taigi įtraukite tą kraštą ir viršūnę 2 į MST.
Į MST įtraukite 2 viršūnę
7 veiksmas: Jungiamieji kraštai tarp neužbaigto MST ir kitų kraštų yra {2, 8}, {2, 3}, {5, 3} ir {5, 4}. Kraštas su minimaliu svoriu yra kraštas {2, 8}, kurio svoris yra 2. Taigi įtraukite šią briauną ir viršūnę 8 į MST.
Pridėkite 8 viršūnę MST
8 veiksmas: Žiūrėkite čia, kad briaunos {7, 8} ir {2, 3} turi tokį patį svorį, kuris yra minimalus. Bet 7 jau yra MST dalis. Taigi mes apsvarstysime kraštą {2, 3} ir įtrauksime tą kraštą ir viršūnę 3 į MST.
Į MST įtraukite 3 viršūnę
9 veiksmas: Belieka įtraukti tik 4 viršūnę. Mažiausias svertinis kraštas nuo neužbaigto MST iki 4 yra {3, 4}.
Į MST įtraukite 4 viršūnę
Galutinė MST struktūra yra tokia, o MST kraštų svoris yra (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
MST struktūra suformuota naudojant aukščiau pateiktą metodą
Pastaba: Jei trečiame žingsnyje būtume pasirinkę kraštą {1, 2}, MST atrodytų taip.
Alternatyvaus MST struktūra, jei MST pasirinkome kraštą {1, 2}
Kaip įdiegti Prim algoritmą?
Atlikite nurodytus veiksmus, kad galėtumėte naudoti Primo algoritmas paminėta aukščiau, norint rasti grafiko MST:
- Sukurkite rinkinį mstSet kuri seka viršūnes, jau įtrauktas į MST.
- Priskirkite rakto reikšmę visoms įvesties grafiko viršūnėms. Inicijuokite visas pagrindines reikšmes kaip INFINITE. Pirmajai viršūnei priskirkite rakto reikšmę 0, kad ji būtų paimta pirmiausia.
- Nors mstSet neapima visų viršūnių
- Pasirinkite viršūnę in to ten nėra mstSet ir turi mažiausią rakto reikšmę.
- Įtraukti in viduje mstSet .
- Atnaujinkite visų gretimų viršūnių rakto reikšmę in . Norėdami atnaujinti raktų reikšmes, kartokite visas gretimas viršūnes.
- Kiekvienai gretimai viršūnei in , jei krašto svoris u-v yra mažesnė nei ankstesnė rakto reikšmė in , atnaujinkite pagrindinę reikšmę kaip svorį u-v .
Pagrindinių reikšmių naudojimo idėja yra pasirinkti minimalų svorio kraštą iš supjaustyti . Pagrindinės reikšmės naudojamos tik toms viršūnėms, kurios dar neįtrauktos į MST, pagrindinė šių viršūnių reikšmė nurodo minimalias svorio briaunas, jungiančias jas su viršūnių, įtrauktų į MST, rinkiniu.
Žemiau pateikiamas metodo įgyvendinimas:
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
substring_index SQL
// 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; }> |
>
>
mini įrankių juosta Excel
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.> |
>
>Išvestis
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Primo algoritmo sudėtingumo analizė:
Laiko sudėtingumas: O(V2), Jei įvestis grafikas vaizduojamas naudojant gretimų sąrašą , tada Prim algoritmo laiko sudėtingumas gali būti sumažintas iki O(E * logV) naudojant dvejetainę krūvą. Šiame įgyvendinime mes visada svarstome, kad apimantis medį būtų pradėtas nuo grafiko šaknies
Pagalbinė erdvė: O(V)
Kiti Prim algoritmo įgyvendinimai:
Toliau pateikiami kai kurie kiti Prim algoritmo įgyvendinimai
- Primo algoritmas gretimų matricų vaizdavimui – Šiame straipsnyje aptarėme Primo algoritmo įgyvendinimo metodą, jei grafikas vaizduojamas gretimų matrica.
- Primo algoritmas gretimų vietų sąrašui pateikti – Šiame straipsnyje aprašomas „Prim“ algoritmo įgyvendinimas grafikams, vaizduojamiems gretimų sąrašu.
- Prim algoritmas naudojant prioritetinę eilę: Šiame straipsnyje aptarėme laiko efektyvų metodą, kaip įgyvendinti Prim algoritmą.
OPTIMIZUOTAS PRIM ALGORITMO POŽIŪRIS:
Intuicija
- Mes paverčiame gretimų matricą į gretimų sąrašą naudodami ArrayList
. - Tada sukuriame poros klasę, kurioje saugome viršūnę ir jos svorį.
- Sąrašą rūšiuojame pagal mažiausią svorį.
- Sukuriame prioritetinę eilę ir pirmąją viršūnę bei jos svorį stumiame eilėje
- Tada mes tiesiog pereiname per jo kraštus ir saugome mažiausią svorį kintamajame, vadinamame metų.
- Pagaliau po visos viršūnės grąžiname ans.
Įgyvendinimas
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]; // Užpildykite gretimų sąrašą briaunomis ir jų svoriais (int i = 0; i int u = briaunos[i][0]; int v = briaunos[i][1]; int wt = briaunos[i][2 ]; adj[u].push_back({v, wt}). aplankytas masyvas, skirtas sekti aplankytų viršūnių vektorių |
>
>
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 = naujas sąrašas[]>>(); 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]; // Krašto svoris const u = p[1]; // Viršūnė prijungta prie briaunos if (aplankė[u]) { tęsti; // Praleisti, jei viršūnė jau aplankyta } res += wt; // Prie aplankyto rezultato pridėkite krašto svorį [u] = true; // Pažymėkite viršūnę kaip aplankytą // Ištirkite gretimas viršūnes (const v of adj[u]) { // v[0] reiškia viršūnę, o v[1] reiškia krašto svorį, jei (!aplankytas[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Prioritetinėje eilėje pridėti gretimą kraštą } } } return res; // Grąžinti minimalaus aprėpimo medžio briaunų svorių sumą } // Pavyzdinis naudojimo const grafas = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Funkcijos iškvietimas console.log(spanningTree(3, 3, graph));>> |
>centrinis vaizdas css4>
Primo algoritmo sudėtingumo analizė:
Laiko sudėtingumas: O(E*log(E)), kur E yra briaunų skaičius
Pagalbinė erdvė: O(V^2), kur V yra viršūnės skaičius
Prim algoritmas ieškant minimalaus apimančio medžio (MST):
Privalumai:
- Prim algoritmas garantuoja, kad suras MST sujungtame, svertiniame grafike.
- Jos laiko sudėtingumas yra O(E log V), naudojant dvejetainę krūvą arba Fibonačio krūvą, kur E yra briaunų skaičius, o V yra viršūnių skaičius.
- Tai gana paprastas algoritmas, kurį reikia suprasti ir įgyvendinti, palyginti su kai kuriais kitais MST algoritmais.
Trūkumai:
- Kaip ir Kruskal algoritmas, Prim algoritmas gali būti lėtas tankiuose grafikuose su daug briaunų, nes jį reikia kartoti per visus kraštus bent vieną kartą.
- Prim algoritmas remiasi prioritetine eile, kuri gali užimti papildomos atminties ir sulėtinti labai didelių grafikų algoritmą.
- Pradinio mazgo pasirinkimas gali paveikti MST išvestį, o tai kai kuriose programose gali būti nepageidautina.