Einführung in den Algorithmus von Prim:
Wir haben diskutiert Kruskals Algorithmus für Minimum Spanning Tree . Wie Kruskals Algorithmus ist auch Prims Algorithmus ein Gieriger Algorithmus . Dieser Algorithmus beginnt immer mit einem einzelnen Knoten und bewegt sich durch mehrere benachbarte Knoten, um unterwegs alle verbundenen Kanten zu erkunden.
Der Algorithmus beginnt mit einem leeren Spannbaum. Die Idee besteht darin, zwei Sätze von Scheitelpunkten beizubehalten. Der erste Satz enthält die Scheitelpunkte, die bereits im MST enthalten sind, und der andere Satz enthält die Scheitelpunkte, die noch nicht enthalten sind. Bei jedem Schritt werden alle Kanten berücksichtigt, die die beiden Mengen verbinden, und aus diesen Kanten wird die Kante mit dem minimalen Gewicht ausgewählt. Nachdem die Kante ausgewählt wurde, wird der andere Endpunkt der Kante auf die Menge verschoben, die MST enthält.
Eine Gruppe von Kanten, die zwei Sätze von Scheitelpunkten in einem Diagramm verbindet, wird aufgerufen Schnitt in der Graphentheorie . Suchen Sie also bei jedem Schritt des Prim-Algorithmus einen Schnitt, wählen Sie die Kante mit dem minimalen Gewicht aus dem Schnitt aus und fügen Sie diesen Scheitelpunkt in den MST-Satz ein (den Satz, der bereits enthaltene Scheitelpunkte enthält).
Wie funktioniert der Algorithmus von Prim?
Die Funktionsweise des Prim-Algorithmus kann anhand der folgenden Schritte beschrieben werden:
Schritt 1: Bestimmen Sie einen beliebigen Scheitelpunkt als Startscheitelpunkt des MST.
Schritt 2: Befolgen Sie die Schritte 3 bis 5, bis es Scheitelpunkte gibt, die nicht im MST enthalten sind (bekannt als Randscheitelpunkt).
Schritt 3: Finden Sie Kanten, die beliebige Baumscheitelpunkte mit den Randscheitelpunkten verbinden.
Schritt 4: Finden Sie das Minimum unter diesen Kanten.
Schritt 5: Füge die ausgewählte Kante zum MST hinzu, wenn sie keinen Kreis bildet.
Schritt 6: Geben Sie das MST zurück und beenden Sie den Vorgang
Notiz: Um einen Zyklus zu bestimmen, können wir die Scheitelpunkte in zwei Sätze unterteilen [ein Satz enthält die in MST enthaltenen Scheitelpunkte und der andere enthält die Randscheitelpunkte.]
Empfohlene Praxis Minimum Spanning Tree Probieren Sie es aus!Illustration des Prim-Algorithmus:
Betrachten Sie die folgende Grafik als Beispiel, für die wir den Minimum Spanning Tree (MST) ermitteln müssen.
Beispiel einer Grafik
Schritt 1: Zunächst wählen wir einen beliebigen Scheitelpunkt aus, der als Startscheitelpunkt des Minimum Spanning Tree fungiert. Hier haben wir den Scheitelpunkt ausgewählt 0 als Startscheitelpunkt.
Als Startscheitelpunkt wird 0 gewählt
Schritt 2: Alle Kanten, die das unvollständige MST und andere Eckpunkte verbinden, sind die Kanten {0, 1} und {0, 7}. Zwischen diesen beiden ist die Kante mit minimalem Gewicht {0, 1}. Beziehen Sie also die Kante und den Scheitelpunkt 1 in das MST ein.
1 wird zum MST hinzugefügt
Schritt 3: Die Kanten, die das unvollständige MST mit anderen Eckpunkten verbinden, sind {0, 7}, {1, 7} und {1, 2}. Unter diesen Kanten beträgt das Mindestgewicht 8, also die Kanten {0, 7} und {1, 2}. Lassen Sie uns hier die Kante {0, 7} und den Scheitelpunkt 7 in das MST einbeziehen. [Wir hätten auch Kante {1, 2} und Scheitelpunkt 2 in das MST einbeziehen können].
7 wird im MST hinzugefügt
Schritt 4: Die Kanten, die das unvollständige MST mit den Randeckpunkten verbinden, sind {1, 2}, {7, 6} und {7, 8}. Fügen Sie die Kante {7, 6} und den Scheitelpunkt 6 im MST hinzu, da dieser das geringste Gewicht hat (d. h. 1).
zusammengesetzter Primärschlüssel6 wird im MST hinzugefügt
Schritt 5: Die Verbindungskanten sind nun {7, 8}, {1, 2}, {6, 8} und {6, 5}. Beziehen Sie die Kante {6, 5} und den Scheitelpunkt 5 in den MST ein, da die Kante unter ihnen das minimale Gewicht (d. h. 2) hat.
Beziehen Sie Scheitelpunkt 5 in das MST ein
Schritt 6: Unter den aktuellen Verbindungskanten hat die Kante {5, 2} das minimale Gewicht. Fügen Sie also diese Kante und den Scheitelpunkt 2 in das MST ein.
Beziehen Sie Scheitelpunkt 2 in das MST ein
Schritt 7: Die Verbindungskanten zwischen dem unvollständigen MST und den anderen Kanten sind {2, 8}, {2, 3}, {5, 3} und {5, 4}. Die Kante mit dem minimalen Gewicht ist Kante {2, 8}, die das Gewicht 2 hat. Beziehen Sie also diese Kante und den Scheitelpunkt 8 in das MST ein.
Fügen Sie Scheitelpunkt 8 im MST hinzu
Schritt 8: Sehen Sie hier, dass die Kanten {7, 8} und {2, 3} beide das gleiche Gewicht haben, was minimal ist. Aber 7 ist bereits Teil von MST. Wir betrachten also die Kante {2, 3} und beziehen diese Kante und den Scheitelpunkt 3 in das MST ein.
Beziehen Sie Scheitelpunkt 3 in MST ein
Schritt 9: Es bleibt nur noch der Scheitelpunkt 4 einzubeziehen. Die minimal gewichtete Kante vom unvollständigen MST zu 4 ist {3, 4}.
Beziehen Sie Scheitelpunkt 4 in das MST ein
Die endgültige Struktur des MST ist wie folgt und das Gewicht der Kanten des MST beträgt (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
Die Struktur des MST wurde mit der oben genannten Methode erstellt
Notiz: Wenn wir im dritten Schritt die Kante {1, 2} ausgewählt hätten, würde das MST wie folgt aussehen.
Struktur des alternativen MST, wenn wir Kante {1, 2} im MST ausgewählt hätten
Wie implementiert man den Algorithmus von Prim?
Befolgen Sie die angegebenen Schritte, um das zu nutzen Prims Algorithmus oben erwähnt, um den MST eines Diagramms zu finden:
- Erstellen Sie ein Set mstSet das die bereits in MST enthaltenen Scheitelpunkte verfolgt.
- Weisen Sie allen Scheitelpunkten im Eingabediagramm einen Schlüsselwert zu. Initialisieren Sie alle Schlüsselwerte als INFINITE. Weisen Sie dem ersten Scheitelpunkt den Schlüsselwert 0 zu, sodass dieser zuerst ausgewählt wird.
- Während mstSet umfasst nicht alle Eckpunkte
- Wählen Sie einen Scheitelpunkt In das steht da nicht drin mstSet und hat einen minimalen Schlüsselwert.
- Enthalten In im mstSet .
- Aktualisieren Sie den Schlüsselwert aller benachbarten Scheitelpunkte von In . Um die Schlüsselwerte zu aktualisieren, durchlaufen Sie alle angrenzenden Scheitelpunkte.
- Für jeden angrenzenden Scheitelpunkt In , wenn das Gewicht der Kante u-v ist kleiner als der vorherige Schlüsselwert von In , aktualisieren Sie den Schlüsselwert als Gewicht von u-v .
Die Idee bei der Verwendung von Schlüsselwerten besteht darin, die minimal gewichtete Kante aus dem auszuwählen schneiden . Die Schlüsselwerte werden nur für Scheitelpunkte verwendet, die noch nicht in MST enthalten sind. Der Schlüsselwert für diese Scheitelpunkte gibt die Mindestgewichtskanten an, die sie mit dem Satz von Scheitelpunkten verbinden, die in MST enthalten sind.
Nachfolgend finden Sie die Umsetzung des Ansatzes:
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-Architektur
Java
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> >// Number of vertices in the graph> >private> static> final> int> V =>5>;> >// A utility function to find the vertex with minimum> >// key value, from the set of vertices not yet included> >// in MST> >int> minKey(>int> key[], Boolean mstSet[])> >{> >// Initialize min value> >int> min = Integer.MAX_VALUE, min_index = ->1>;> >for> (>int> v =>0>; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
>
>
Python3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> [[>0> for> column>in> range>(vertices)]> >for> row>in> range>(vertices)]> ># A utility function to print> ># the constructed MST stored in parent[]> >def> printMST(>self>, parent):> >print>(>'Edge Weight'>)> >for> i>in> range>(>1>,>self>.V):> >print>(parent[i],>'-'>, i,>' '>,>self>.graph[i][parent[i]])> ># A utility function to find the vertex with> ># minimum distance value, from the set of vertices> ># not yet included in shortest path tree> >def> minKey(>self>, key, mstSet):> ># Initialize min value> >min> => sys.maxsize> >for> v>in> range>(>self>.V):> >if> key[v] <>min> and> mstSet[v]>=>=> False>:> >min> => key[v]> >min_index>=> v> >return> min_index> ># Function to construct and print MST for a graph> ># represented using adjacency matrix representation> >def> primMST(>self>):> ># Key values used to pick minimum weight edge in cut> >key>=> [sys.maxsize]>*> self>.V> >parent>=> [>None>]>*> self>.V># Array to store constructed MST> ># Make key 0 so that this vertex is picked as first vertex> >key[>0>]>=> 0> >mstSet>=> [>False>]>*> self>.V> >parent[>0>]>=> ->1> # First node is always the root of> >for> cout>in> range>(>self>.V):> ># Pick the minimum distance vertex from> ># the set of vertices not yet processed.> ># u is always equal to src in first iteration> >u>=> self>.minKey(key, mstSet)> ># Put the minimum distance vertex in> ># the shortest path tree> >mstSet[u]>=> True> ># Update dist value of the adjacent vertices> ># of the picked vertex only if the current> ># distance is greater than new distance and> ># the vertex in not in the shortest path tree> >for> v>in> range>(>self>.V):> ># graph[u][v] is non zero only for adjacent vertices of m> ># mstSet[v] is false for vertices not yet included in MST> ># Update the key only if graph[u][v] is smaller than key[v]> >if> self>.graph[u][v]>>0> and> mstSet[v]>=>=> False> > >and> key[v]>>self>.graph[u][v]:> >key[v]>=> self>.graph[u][v]> >parent[v]>=> u> >self>.printMST(parent)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph(>5>)> >g.graph>=> [[>0>,>2>,>0>,>6>,>0>],> >[>2>,>0>,>3>,>8>,>5>],> >[>0>,>3>,>0>,>0>,>7>],> >[>6>,>8>,>0>,>0>,>9>],> >[>0>,>5>,>7>,>9>,>0>]]> >g.primMST()> # Contributed by Divyanshu Mehta> |
>
>
C#
Ridhima Tiwari
// 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.> |
>
>Ausgabe
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Komplexitätsanalyse des Prim-Algorithmus:
Zeitkomplexität: O(V2), Wenn die Eingabe Der Graph wird mithilfe einer Adjazenzliste dargestellt , dann kann die Zeitkomplexität des Prim-Algorithmus mit Hilfe eines binären Heaps auf O(E * logV) reduziert werden. In dieser Implementierung gehen wir davon aus, dass der Spanning Tree immer an der Wurzel des Diagramms beginnt
Hilfsraum: O(V)
Andere Implementierungen des Prim-Algorithmus:
Nachfolgend sind einige andere Implementierungen des Prim-Algorithmus aufgeführt
- Prims Algorithmus zur Darstellung der Adjazenzmatrix – In diesem Artikel haben wir die Methode zur Implementierung des Prim-Algorithmus diskutiert, wenn der Graph durch eine Adjazenzmatrix dargestellt wird.
- Prims Algorithmus zur Darstellung von Adjazenzlisten – In diesem Artikel wird die Implementierung des Prim-Algorithmus für Diagramme beschrieben, die durch eine Adjazenzliste dargestellt werden.
- Prims Algorithmus unter Verwendung der Prioritätswarteschlange: In diesem Artikel haben wir einen zeiteffizienten Ansatz zur Implementierung des Prim-Algorithmus diskutiert.
OPTIMIERTER ANSATZ DES PRIM-ALGORITHMUS:
Intuition
- Wir wandeln die Adjazenzmatrix mit in eine Adjazenzliste um Anordnungsliste
. - Dann erstellen wir eine Pair-Klasse, um den Scheitelpunkt und seine Gewichtung zu speichern.
- Wir sortieren die Liste nach dem niedrigsten Gewicht.
- Wir erstellen eine Prioritätswarteschlange und verschieben den ersten Scheitelpunkt und sein Gewicht in die Warteschlange
- Dann durchlaufen wir einfach seine Kanten und speichern das geringste Gewicht in einer Variablen namens Jahre.
- Schließlich, nach all dem Scheitelpunkt, geben wir die ans zurück.
Implementierung
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]; // Fülle die Adjazenzliste mit Kanten und ihren Gewichten für (int i = 0; i int u = Edges[i][0]; int v = Edges[i][1]; int wt = Edges[i][2 ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); // Eine Prioritätswarteschlange erstellen, um Kanten mit ihren Gewichten zu speichern Visited-Array, um den Vektor der besuchten Scheitelpunkte zu verfolgen |
>
>
Java
beginnt mit 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))> |
>
Algorithmen binäre Suche
>
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 = new 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]; // Gewicht der Kante const u = p[1]; // Vertex mit der Kante verbunden if (visited[u]) { continue; // Überspringen, wenn der Scheitelpunkt bereits besucht ist } res += wt; // Füge das Kantengewicht zum Ergebnis hinzu besuchte[u] = true; // Markiere den Scheitelpunkt als besucht // Erkunde die angrenzenden Scheitelpunkte für (const v of adj[u]) { // v[0] repräsentiert den Scheitelpunkt und v[1] repräsentiert das Kantengewicht if (!visited[v[0 ]]) { pq.enqueue([v[1], v[0]]); // Die angrenzende Kante zur Prioritätswarteschlange hinzufügen } } } return res; // Die Summe der Kantengewichte des Minimum Spanning Tree zurückgeben } // Beispielverwendung const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Funktionsaufruf console.log(spanningTree(3, 3, graph));> |
>
>Ausgabe
4>
Komplexitätsanalyse des Prim-Algorithmus:
Zeitkomplexität: O(E*log(E)) wobei E die Anzahl der Kanten ist
Hilfsraum: O(V^2) wobei V die Anzahl der Scheitelpunkte ist
Prims Algorithmus zum Finden des Minimum Spanning Tree (MST):
Vorteile:
- Der Algorithmus von Prim findet garantiert den MST in einem verbundenen, gewichteten Diagramm.
- Es hat eine zeitliche Komplexität von O(E log V) unter Verwendung eines binären Heaps oder Fibonacci-Heaps, wobei E die Anzahl der Kanten und V die Anzahl der Eckpunkte ist.
- Im Vergleich zu einigen anderen MST-Algorithmen ist es ein relativ einfach zu verstehender und zu implementierender Algorithmus.
Nachteile:
- Wie der Kruskal-Algorithmus kann auch der Prim-Algorithmus bei dichten Graphen mit vielen Kanten langsam sein, da alle Kanten mindestens einmal durchlaufen werden müssen.
- Der Algorithmus von Prim basiert auf einer Prioritätswarteschlange, die zusätzlichen Speicher beanspruchen und den Algorithmus bei sehr großen Diagrammen verlangsamen kann.
- Die Wahl des Startknotens kann sich auf die MST-Ausgabe auswirken, was in manchen Anwendungen möglicherweise nicht wünschenswert ist.