Johdatus Primin algoritmiin:
Olemme keskustelleet Kruskalin algoritmi Minimum Spanning Tree . Kuten Kruskalin algoritmi, Primin algoritmi on myös a Ahne algoritmi . Tämä algoritmi alkaa aina yhdestä solmusta ja liikkuu useiden vierekkäisten solmujen läpi tutkiakseen kaikkia matkan varrella olevia reunoja.
Algoritmi alkaa tyhjästä virittävästä puusta. Ajatuksena on säilyttää kaksi kärkijoukkoa. Ensimmäinen joukko sisältää pisteet, jotka jo sisältyvät MST:hen, ja toinen joukko sisältää pisteet, joita ei vielä ole sisällytetty. Jokaisessa vaiheessa se ottaa huomioon kaikki reunat, jotka yhdistävät kaksi sarjaa, ja valitsee näistä reunoista vähimmäispainoreunan. Reunan poimimisen jälkeen se siirtää reunan toisen päätepisteen MST:n sisältävään joukkoon.
Reunaryhmää, joka yhdistää kaksi graafin kärkijoukkoa, kutsutaan leikata graafiteoriassa . Joten Primin algoritmin jokaisessa vaiheessa etsi leikkaus, valitse leikkauksen vähimmäispainoreuna ja sisällytä tämä kärki MST-joukkoon (joukko, joka sisältää jo mukana olevat kärjet).
Kuinka Primin algoritmi toimii?
Primin algoritmin toimintaa voidaan kuvata seuraavien vaiheiden avulla:
roomalaiset numerot 1-100
Vaihe 1: Määritä mielivaltainen kärki MST:n aloituspisteeksi.
Vaihe 2: Noudata vaiheita 3 - 5, kunnes on pisteitä, jotka eivät sisälly MST:hen (tunnetaan nimellä fringe vertex).
Vaihe 3: Etsi reunat, jotka yhdistävät minkä tahansa puun kärjen reunapisteisiin.
Vaihe 4: Etsi näiden reunojen joukosta minimi.
Vaihe 5: Lisää valittu reuna MST:hen, jos se ei muodosta sykliä.
Vaihe 6: Palauta MST ja poistu
Huomautus: Syklin määrittämiseksi voimme jakaa kärjet kahdeksi joukoksi [yksi joukko sisältää MST:n pisteet ja toinen reunapisteet.]
Suositeltu harjoitus, vähintään ulottuva puu Kokeile!Kuva Primin algoritmista:
Tarkastellaan seuraavaa kuvaajaa esimerkkinä, jota varten meidän on löydettävä vähimmäisvälipuu (MST).
Esimerkki kaaviosta
Vaihe 1: Ensin valitaan mielivaltainen kärkipiste, joka toimii Minimum Spanning Treen aloituspisteenä. Tässä olemme valinneet huippupisteen 0 aloituspisteenä.
0 on valittu aloituspisteeksi
Vaihe 2: Kaikki epätäydellistä MST:tä ja muita pisteitä yhdistävät reunat ovat reunat {0, 1} ja {0, 7}. Näiden kahden välissä minimipainoinen reuna on {0, 1}. Sisällytä siis reuna ja kärkipiste 1 MST:hen.
1 lisätään MST:hen
Vaihe 3: Reunat, jotka yhdistävät epätäydellisen MST:n muihin pisteisiin ovat {0, 7}, {1, 7} ja {1, 2}. Näiden reunojen joukossa vähimmäispaino on 8, joka on reunoista {0, 7} ja {1, 2}. Sisällytetään tähän MST:n reuna {0, 7} ja kärki 7. [Olemme voineet sisällyttää myös reunan {1, 2} ja kärjen 2 MST:hen].
7 on lisätty MST:hen
Vaihe 4: Reunat, jotka yhdistävät epätäydellisen MST:n reunapisteisiin ovat {1, 2}, {7, 6} ja {7, 8}. Lisää reuna {7, 6} ja kärkipiste 6 MST:ssä, koska sillä on pienin paino (eli 1).
6 on lisätty MST:hen
Vaihe 5: Liitosreunat ovat nyt {7, 8}, {1, 2}, {6, 8} ja {6, 5}. Sisällytä reuna {6, 5} ja kärki 5 MST:hen, koska reunalla on pienin paino (eli 2) niiden joukossa.
Sisällytä huippupiste 5 MST:hen
Vaihe 6: Nykyisistä yhdistävistä reunoista reunalla {5, 2} on vähimmäispaino. Sisällytä siis tuo reuna ja kärkipiste 2 MST:hen.
Sisällytä vertex 2 MST:hen
Vaihe 7: Epätäydellisen MST:n ja muiden reunojen väliset yhdistävät reunat ovat {2, 8}, {2, 3}, {5, 3} ja {5, 4}. Minimipainoinen reuna on reuna {2, 8}, jonka paino on 2. Sisällytä siis tämä reuna ja kärki 8 MST:hen.
Lisää vertex 8 MST:hen
Vaihe 8: Katso tästä, että reunoilla {7, 8} ja {2, 3} on sama paino, joka on minimi. Mutta 7 on jo osa MST:tä. Joten tarkastelemme reunaa {2, 3} ja sisällytämme sen reunan ja kärjen 3 MST:hen.
Sisällytä huippupiste 3 MST:hen
Vaihe 9: Vain kärki 4 jää mukaan. Pienin painotettu reuna epätäydellisestä MST:stä 4:ään on {3, 4}.
Sisällytä vertex 4 MST:hen
MST:n lopullinen rakenne on seuraava ja MST:n reunojen paino on (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
MST:n rakenne muodostettiin käyttämällä yllä olevaa menetelmää
Huomautus: Jos olisimme valinneet reunan {1, 2} kolmannessa vaiheessa, MST näyttäisi seuraavalta.
Vaihtoehtoisen MST:n rakenne, jos olisimme valinneet reunan {1, 2} MST:ssä
Kuinka Primin algoritmi otetaan käyttöön?
Käytä annettuja ohjeita noudattamalla Primin algoritmi edellä mainitut kaavion MST:n löytämiseksi:
- Luo sarja mstSet joka pitää kirjaa pisteistä, jotka jo sisältyvät MST:hen.
- Määritä avainarvo kaikille syötekaavion pisteille. Alusta kaikkien avainarvojen arvoksi INFINITE. Määritä avaimen arvoksi 0 ensimmäiselle kärjelle, jotta se valitaan ensin.
- Sillä aikaa mstSet ei sisällä kaikkia huippuja
- Valitse huippupiste sisään joka ei ole siellä mstSet ja sillä on vähimmäisavaimen arvo.
- Sisältää sisään in mstSet .
- Päivitä kaikkien vierekkäisten kärkien avainarvo sisään . Päivitä avainarvot iteroimalla kaikki vierekkäiset kärjet.
- Jokaiselle viereiselle kärkipisteelle sisään , jos reunan paino u-v on pienempi kuin edellinen avainarvo sisään , päivitä avainarvo painona u-v .
Avainarvojen käytön ideana on valita vähimmäispainoreuna leikata . Avainarvoja käytetään vain pisteille, jotka eivät vielä sisälly MST:hen, näiden pisteiden avainarvo ilmaisee vähimmäispainoreunat, jotka yhdistävät ne MST:n sisältämiin kärkijoukkoon.
Alla on lähestymistavan toteutus:
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> |
>
>
Python 3
# 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.> |
>
>Lähtö
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Primin algoritmin monimutkaisuusanalyysi:
Aika monimutkaisuus: O(V2), Jos syöte kaavio esitetään vierekkäisyysluettelolla , niin Primin algoritmin aikamonimutkaisuus voidaan pienentää arvoon O(E * logV) binäärikeon avulla. Tässä toteutuksessa harkitsemme aina virittävän puun alkavan graafin juuresta
Aputila: O(V)
Muita Primin algoritmin toteutuksia:
Alla on joitain muita Primin algoritmin toteutuksia
- Primin algoritmi vierekkäismatriisiesitykselle – Tässä artikkelissa olemme käsitelleet menetelmää Primin algoritmin toteuttamiseksi, jos graafia edustaa viereisyysmatriisi.
- Primin algoritmi vierekkäisyysluettelon esittämiseen – Tässä artikkelissa Primin algoritmin toteutus kuvataan vierekkäisyysluettelon edustamille kaavioille.
- Primin algoritmi Priority Queue:n avulla: Tässä artikkelissa olemme keskustelleet aikatehokkaasta lähestymistavasta Primin algoritmin toteuttamiseen.
PRIM:N ALGORITMI OPTIMOITU LÄHESTYMISTAPA:
Intuitio
- Muunnamme viereisyysmatriisin viereisyysluetteloksi käyttämällä ArrayList
. - Sitten luodaan Pair-luokka tallentamaan kärkipiste ja sen paino.
- Lajittelemme listan pienimmän painon mukaan.
- Luomme prioriteettijonon ja työnnämme ensimmäisen kärjen ja sen painon jonoon
- Sitten vain kuljemme sen reunojen läpi ja tallennamme pienimmän painon muuttujaan nimeltä vuotta.
- Lopuksi kaikkien kärjen jälkeen palautetaan ans.
Toteutus
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]; // Täytä vierekkäisyyslista reunoilla ja niiden painoilla kohteelle (int i = 0; i int u = reunat[i][0]; int v = reunat[i][1]; int wt = reunat[i][2 ]; adj[u].push_back({v, wt}); vierailtu taulukko pitääksesi kirjaa vierailtujen huippupisteiden vektoreista |
>
>
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)); } }> |
>
>
Python 3
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 = uusi Listint[]>>(); 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]; // Reunan paino const u = p[1]; // Reunaan yhdistetty kärki if (vieraillut[u]) { jatka; // Ohita, jos kärjessä on jo käyty } res += wt; // Lisää reunan painotus vierailltuun tulokseen[u] = true; // Merkitse kärki vierailluksi // Tutki vierekkäisiä kärkipisteitä kohteelle (const v of adj[u]) { // v[0] edustaa kärkeä ja v[1] edustaa reunan painoa, jos (!visited[v[0] ]]) { pq.enqueue([v[1], v[0]]); // Lisää viereinen reuna prioriteettijonoon } } } return res; // Palauttaa minimivirityspuun reunapainojen summan } // Käyttöesimerkki const-graafi = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Funktio kutsu console.log(spanningTree(3, 3, graph));>> |
>4>
Primin algoritmin monimutkaisuusanalyysi:
Aika monimutkaisuus: O(E*log(E)) missä E on reunojen lukumäärä
Aputila: O(V^2) missä V on kärjen lukumäärä
Primin algoritmi minimivirittävän puun (MST) löytämiseksi:
Edut:
- Primin algoritmi löytää taatusti MST:n yhdistetystä painotetusta graafista.
- Sen aikamonimutkaisuus on O(E log V) käyttämällä binäärikekoa tai Fibonacci-kekoa, missä E on reunojen lukumäärä ja V on kärkien lukumäärä.
- Se on suhteellisen yksinkertainen algoritmi ymmärtää ja toteuttaa verrattuna joihinkin muihin MST-algoritmeihin.
Haitat:
- Kuten Kruskalin algoritmi, Primin algoritmi voi olla hidas tiheissä graafisissa, joissa on useita reunoja, koska se vaatii iteroinnin kaikkien reunojen yli vähintään kerran.
- Primin algoritmi luottaa prioriteettijonoon, joka voi viedä ylimääräistä muistia ja hidastaa algoritmia erittäin suurilla kaavioilla.
- Aloitussolmun valinta voi vaikuttaa MST-lähtöön, mikä ei ehkä ole toivottavaa joissakin sovelluksissa.