Der Algorithmus von Prim ist ein Minimum-Spanning-Tree-Algorithmus, der einen Graphen als Eingabe nimmt und eine Teilmenge der Kanten dieses Graphen findet, die einen Baum bildet, der jeden Scheitelpunkt enthält und auch die minimale Summe von Gewichten unter allen Bäumen hat, die aus dem Graphen gebildet werden können .
So funktioniert der Algorithmus von Prim
Es fällt unter eine Klasse von Algorithmen, die als "greedy" Algorithmen* bezeichnet werden und ein lokales Optimum in der Hoffnung finden, ein globales Optimum zu finden.
Wir beginnen an einem Scheitelpunkt und fügen Kanten mit dem niedrigsten Gewicht hinzu, bis wir unser Ziel erreichen.
Die Schritte zur Implementierung von Prims Algorithmus sind wie folgt:
- Initialisiere einen minimalen Spannbaum mit einem beliebigen Scheitelpunkt.
- Finde alle Kanten, die den Baum mit neuen Knoten verbinden, finde das Minimum und füge es dem Baum hinzu.
- Wiederholen Sie Schritt 2 so lange, bis Sie den minimalen Spannbaum erhalten.
Prima-Algorithmus-Beispiel
Algorithmus von ##Prim. Pseudocode.
Der Pseudocode für den Algorithmus von Prim zeigt, wie wir zwei Sätze von Scheitelpunkten U und VU erzeugen. U enthält eine Liste von besuchten Scheitelpunkten und VU eine Liste von nicht besuchten Scheitelpunkten. Wir verschieben einen Knoten nach dem anderen von der Menge VU zur Menge U und verbinden dabei die Kante mit dem niedrigsten Gewicht.
Implementierung des Algorithmus von Prim in C++
Das folgende Programm implementiert den Algorithmus von Prim in C++. Obwohl er eine Adjazenzmatrix verwendet, um den Graphen darzustellen, kann dieser Algorithmus auch unter Verwendung einer Adjazenzliste implementiert werden, um seine Effizienz zu verbessern.
#include <iostream>
#include <cstring>
using namespace std;
#define INF 9999999
// number of vertices in grapj
#define V 5
// create a 2d array of size 5x5
//for adjacency matrix to represent graph
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}
};
int main () {
int no_edge; // number of edge
// create a array to track selected vertex
// selected will become true otherwise false
int selected[V];
// set selected false initially
memset (selected, false, sizeof (selected));
// set number of edge to 0
no_edge = 0;
// the number of egde in minimum spanning tree will be
// always less than (V -1), where V is number of vertices in
//graph
// choose 0th vertex and make it true
selected[0] = true;
int x; // row number
int y; // col number
// print for edge and weight
cout << "Edge" << " : " << "Weight";
cout << endl;
while (no_edge < V - 1) {
//For every vertex in the set S, find the all adjacent vertices
// , calculate the distance from the vertex selected at step 1.
// if the vertex is already in the set S, discard it otherwise
//choose another vertex nearest to selected vertex at step 1.
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) { // not in selected and there is an edge
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;
}
Wenn wir den obigen Code ausführen, erhalten wir folgende Ausgabe:
Edge : Weight 0 - 1 : 9 1 - 3 : 19 3 - 4 : 31 3 - 2 : 51
Prims Algorithmus vs. Kraskals
Kruskals Algorithmus ist ein weiterer beliebter Minimum-Spanning-Tree-Algorithmus, der eine andere Logik verwendet, um den MST-Graphen zu finden. Anstatt oben zu beginnen, sortiert Kruskals Algorithmus alle Kanten von niedrigem Gewicht zu hohem Gewicht und fährt fort, die niedrigsten Kanten hinzuzufügen, wobei diejenigen Kanten ignoriert werden, die einen Zyklus erzeugen.
