In diesem Artikel werden wir den Algorithmus des Prims diskutieren. Zusammen mit dem Algorithmus werden wir auch die Komplexität, Funktionsweise, Beispiele und Implementierung des Prim-Algorithmus sehen.
Bevor wir mit dem Hauptthema beginnen, sollten wir die grundlegenden und wichtigen Begriffe wie Spanning Tree und Minimum Spanning Tree besprechen.
Spannender Baum - Ein Spanning Tree ist der Teilgraph eines ungerichteten zusammenhängenden Graphen.
Minimaler Spannbaum - Der minimale Spannbaum kann als der Spannbaum definiert werden, in dem die Summe der Kantengewichte minimal ist. Das Gewicht des Spannbaums ist die Summe der Gewichte, die den Kanten des Spannbaums gegeben werden.
Beginnen wir nun mit dem Hauptthema.
Prims Algorithmus ist ein gieriger Algorithmus, der verwendet wird, um den minimalen Spannbaum aus einem Diagramm zu finden. Der Algorithmus von Prim findet die Teilmenge der Kanten, die jeden Scheitelpunkt des Diagramms umfasst, sodass die Summe der Gewichte der Kanten minimiert werden kann.
Der Algorithmus von Prim beginnt mit dem einzelnen Knoten und untersucht bei jedem Schritt alle angrenzenden Knoten mit allen Verbindungskanten. Die Kanten mit den minimalen Gewichten, die keine Zyklen im Diagramm verursachen, wurden ausgewählt.
Wie funktioniert der Algorithmus des Prims?
Der Algorithmus von Prim ist ein gieriger Algorithmus, der von einem Scheitelpunkt aus beginnt und so lange die Kanten mit dem geringsten Gewicht hinzufügt, bis das Ziel erreicht ist. Die Schritte zur Implementierung des Prim-Algorithmus sind wie folgt angegeben:
- Zuerst müssen wir ein MST mit dem zufällig ausgewählten Scheitelpunkt initialisieren.
- Jetzt müssen wir alle Kanten finden, die den Baum im obigen Schritt mit den neuen Eckpunkten verbinden. Wählen Sie aus den gefundenen Kanten die minimale Kante aus und fügen Sie sie dem Baum hinzu.
- Wiederholen Sie Schritt 2, bis der minimale Spannbaum gebildet ist.
Die Anwendungen des Prim-Algorithmus sind:
- Der Algorithmus von Prim kann beim Netzwerkdesign verwendet werden.
- Es können Netzwerkzyklen erstellt werden.
- Es kann auch zum Verlegen von Elektrokabeln verwendet werden.
Beispiel für den Algorithmus von Prim
Sehen wir uns nun die Funktionsweise des Prim-Algorithmus anhand eines Beispiels an. Anhand eines Beispiels lässt sich der Algorithmus des Prims leichter verstehen.
Angenommen, ein gewichteter Graph ist -
Schritt 1 - Zuerst müssen wir einen Scheitelpunkt aus dem obigen Diagramm auswählen. Wählen wir B.
Datum und Uhrzeit des Typoskripts
Schritt 2 - Jetzt müssen wir die kürzeste Kante vom Scheitelpunkt B auswählen und hinzufügen. Es gibt zwei Kanten vom Scheitelpunkt B, nämlich B nach C mit dem Gewicht 10 und Kante B nach D mit dem Gewicht 4. Unter den Kanten hat die Kante BD das minimale Gewicht . Fügen Sie es also zum MST hinzu.
Schritt 3 - Wählen Sie nun unter allen anderen Kanten erneut die Kante mit dem geringsten Gewicht aus. In diesem Fall sind die Kanten DE und CD solche Kanten. Fügen Sie sie zum MST hinzu und untersuchen Sie die angrenzenden Kanten von C, d. h. E und A. Wählen Sie also die Kante DE aus und fügen Sie sie zum MST hinzu.
Schritt 4 - Wählen Sie nun die Edge-CD aus und fügen Sie sie dem MST hinzu.
Schritt 5 – Wählen Sie nun die Edge-CA aus. Hier können wir die Kante CE nicht auswählen, da dies einen Zyklus zum Diagramm erzeugen würde. Wählen Sie also die Edge-CA aus und fügen Sie sie dem MST hinzu.
Der in Schritt 5 erstellte Graph ist also der minimale Spannbaum des gegebenen Graphen. Die Kosten für das MST sind unten angegeben:
Kosten für MST = 4 + 2 + 1 + 3 = 10 Einheiten.
Algorithmus
Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT
Komplexität des Prim-Algorithmus
Sehen wir uns nun die zeitliche Komplexität des Prim-Algorithmus an. Die Laufzeit des Prim-Algorithmus hängt von der Verwendung der Datenstruktur für den Graphen und der Reihenfolge der Kanten ab. Die folgende Tabelle zeigt einige Auswahlmöglichkeiten:
| Datenstruktur, die für das minimale Kantengewicht verwendet wird | Zeitkomplexität |
|---|---|
| Adjazenzmatrix, lineare Suche | O(|V|2) |
| Adjazenzliste und binärer Heap | O(|E| log |V|) |
| Adjazenzliste und Fibonacci-Heap | O(|E|+ |V| log |V|) |
Der Algorithmus von Prim kann einfach mithilfe der Adjazenzmatrix- oder Adjazenzlistendiagrammdarstellung implementiert werden. Um die Kante mit der minimalen Gewichtung hinzuzufügen, muss ein Array von Gewichtungen linear durchsucht werden. Es erfordert O(|V|2) Laufzeit. Es kann weiter verbessert werden, indem die Implementierung von Heap verwendet wird, um die Kanten mit minimalem Gewicht in der inneren Schleife des Algorithmus zu finden.
Die zeitliche Komplexität des Prim-Algorithmus beträgt O(E logV) oder O(V logV), wobei E die Zahl ist. der Kanten und V ist die Anzahl der Kanten. von Eckpunkten.
Implementierung des Prim-Algorithmus
Sehen wir uns nun die Implementierung des Prim-Algorithmus an.
Programm: Schreiben Sie ein Programm, um den Algorithmus von prim in der Sprache C zu implementieren.
#include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
weight
'); printf(' %d
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>