algorithm
Prims Algorithmus
Suche…
Einführung in den Algorithmus von Prim
Nehmen wir an, wir haben 8 Häuser. Wir wollen Telefonleitungen zwischen diesen Häusern einrichten. Die Kante zwischen den Häusern repräsentiert die Kosten für die Einstellung der Linie zwischen zwei Häusern.
Unsere Aufgabe ist es, Leitungen so einzurichten, dass alle Häuser miteinander verbunden sind und die Kosten für die Einrichtung der gesamten Verbindung minimal sind. Wie finden wir das heraus? Wir können den Algorithmus von Prim verwenden .
Der Algorithmus von Prim ist ein gieriger Algorithmus, der einen minimalen Spannbaum für einen gewichteten ungerichteten Graphen findet. Das heißt, es findet eine Teilmenge der Kanten, die einen Baum bilden, der jeden Knoten enthält, wobei die Gesamtgewichtigkeit aller Kanten im Baum minimiert wird. Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt und später wiederentdeckt und 1957 von dem Informatiker Robert Clay Prim und Edsger Wybe Dijkstra im Jahr 1959 erneut veröffentlicht. Er ist auch als DJP-Algorithmus , Jarniks Algorithmus , Prim-Jarnik-Algorithmus oder Prim-Dijsktra bekannt Algorithmus .
Schauen wir uns zuerst die technischen Begriffe an. Wenn wir einen Graphen S mit einigen Knoten und Kanten eines ungerichteten Graphen G erstellen, wird S als Untergraph des Graphen G bezeichnet . Nun wird S nur dann als Spanning Tree bezeichnet, wenn:
- Es enthält alle Knoten von G.
- Es ist ein Baum, dh es gibt keinen Zyklus und alle Knoten sind verbunden.
- Es gibt (n-1) Kanten im Baum, wobei n die Anzahl der Knoten in G ist .
Es können viele Spannbaums eines Diagramms vorhanden sein. Der Minimum Spanning Tree eines gewichteten ungerichteten Graphen ist ein Baum, bei dem die Summe der Kantengewichte minimal ist. Jetzt verwenden wir den Algorithmus von Prim , um den minimalen Spannbaum herauszufinden. So richten Sie die Telefonleitungen in unserem Beispieldiagramm so ein, dass die Kosten für die Einrichtung minimal sind.
Zunächst werden wir einen Quellknoten auswählen. Sagen wir, Knoten-1 ist unsere Quelle . Jetzt fügen wir den Rand von Knoten-1 hinzu , der die Mindestkosten für unseren Subgraph hat. Hier markieren wir die Kanten, die sich im Subgraph befinden, mit der Farbe Blau . Hier ist 1-5 unser gewünschter Rand. 
Nun betrachten wir alle Kanten von Knoten-1 und Knoten-5 und nehmen das Minimum vor. Da 1-5 bereits markiert ist, nehmen wir 1-2 . 
Diesmal betrachten wir Knoten-1 , Knoten-2 und Knoten-5 und nehmen die minimale Kante, die 5-4 beträgt. 
Der nächste Schritt ist wichtig. Von Knoten-1 , Knoten-2 , Knoten-5 und Knoten-4 beträgt die minimale Kante 2-4 . Wenn wir diesen auswählen, wird in unserem Subgraph ein Zyklus erstellt. Dies liegt daran, dass node-2 und node-4 bereits in unserem Subgraph enthalten sind. Von Vorteil 2-4 zu profitieren, nützt uns also nicht. Wir werden die Kanten so auswählen, dass ein neuer Knoten in unserem Subgraph eingefügt wird . Wir wählen also die Kante 4-8 . 
Wenn wir so weitermachen, wählen wir die Kanten 8-6 , 6-7 und 4-3 . Unser Subgraph wird wie folgt aussehen: 
Dies ist unser gewünschter Subgraph, der uns den minimalen Spannbaum gibt. Wenn wir die Kanten entfernen, die wir nicht ausgewählt haben, erhalten wir: 
Dies ist unser Minimum Spanning Tree (MST). Die Kosten für die Einrichtung der Telefonverbindungen betragen also: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . Die Anzahl der Häuser und ihre Verbindungen werden in der Grafik dargestellt. Es kann mehrere MST eines Graphen geben. Es hängt von dem Quellknoten wir wählen.
Der Pseudocode des Algorithmus ist unten angegeben:
Procedure PrimsMST(Graph): // here Graph is a non-empty connected weighted graph
Vnew[] = {x} // New subgraph Vnew with source node x
Enew[] = {}
while Vnew is not equal to V
u -> a node from Vnew
v -> a node that is not in Vnew such that edge u-v has the minimum cost
// if two nodes have same weight, pick any of them
add v to Vnew
add edge (u, v) to Enew
end while
Return Vnew and Enew
Komplexität:
Die zeitliche Komplexität des obigen naiven Ansatzes ist O (V²) . Es verwendet eine Adjazenzmatrix. Wir können die Komplexität mithilfe der Prioritätswarteschlange reduzieren. Wenn wir einen neuen Knoten zu Vnew hinzufügen, können wir die angrenzenden Kanten in der Prioritätswarteschlange hinzufügen. Dann die minimale gewichtete Kante daraus entfernen. Dann ist die Komplexität: O (ElogE) , wobei E die Anzahl der Kanten ist. Wieder kann ein binärer Heap erstellt werden, um die Komplexität auf O (ElogV) zu reduzieren.
Der Pseudo-Code mit Priority Queue ist unten angegeben:
Procedure MSTPrim(Graph, source):
for each u in V
key[u] := inf
parent[u] := NULL
end for
key[source] := 0
Q = Priority_Queue()
Q = V
while Q is not empty
u -> Q.pop
for each v adjacent to i
if v belongs to Q and Edge(u,v) < key[v] // here Edge(u, v) represents
// cost of edge(u, v)
parent[v] := u
key[v] := Edge(u, v)
end if
end for
end while
Hier speichert key [] die minimalen Kosten für das Durchlaufen von node-v . Parent [] wird zum Speichern des Parent-Knotens verwendet. Es ist nützlich, um den Baum zu durchqueren und zu drucken.
Unten ist ein einfaches Programm in Java:
import java.util.*;
public class Graph
{
private static int infinite = 9999999;
int[][] LinkCost;
int NNodes;
Graph(int[][] mat)
{
int i, j;
NNodes = mat.length;
LinkCost = new int[NNodes][NNodes];
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
{
LinkCost[i][j] = mat[i][j];
if ( LinkCost[i][j] == 0 )
LinkCost[i][j] = infinite;
}
}
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
if ( LinkCost[i][j] < infinite )
System.out.print( " " + LinkCost[i][j] + " " );
else
System.out.print(" * " );
System.out.println();
}
}
public int unReached(boolean[] r)
{
boolean done = true;
for ( int i = 0; i < r.length; i++ )
if ( r[i] == false )
return i;
return -1;
}
public void Prim( )
{
int i, j, k, x, y;
boolean[] Reached = new boolean[NNodes];
int[] predNode = new int[NNodes];
Reached[0] = true;
for ( k = 1; k < NNodes; k++ )
{
Reached[k] = false;
}
predNode[0] = 0;
printReachSet( Reached );
for (k = 1; k < NNodes; k++)
{
x = y = 0;
for ( i = 0; i < NNodes; i++ )
for ( j = 0; j < NNodes; j++ )
{
if ( Reached[i] && !Reached[j] &&
LinkCost[i][j] < LinkCost[x][y] )
{
x = i;
y = j;
}
}
System.out.println("Min cost edge: (" +
+ x + "," +
+ y + ")" +
"cost = " + LinkCost[x][y]);
predNode[y] = x;
Reached[y] = true;
printReachSet( Reached );
System.out.println();
}
int[] a= predNode;
for ( i = 0; i < NNodes; i++ )
System.out.println( a[i] + " --> " + i );
}
void printReachSet(boolean[] Reached )
{
System.out.print("ReachSet = ");
for (int i = 0; i < Reached.length; i++ )
if ( Reached[i] )
System.out.print( i + " ");
//System.out.println();
}
public static void main(String[] args)
{
int[][] conn = {{0,3,0,2,0,0,0,0,4}, // 0
{3,0,0,0,0,0,0,4,0}, // 1
{0,0,0,6,0,1,0,2,0}, // 2
{2,0,6,0,1,0,0,0,0}, // 3
{0,0,0,1,0,0,0,0,8}, // 4
{0,0,1,0,0,0,8,0,0}, // 5
{0,0,0,0,0,8,0,0,0}, // 6
{0,4,2,0,0,0,0,0,0}, // 7
{4,0,0,0,8,0,0,0,0} // 8
};
Graph G = new Graph(conn);
G.Prim();
}
}
Kompilieren Sie den obigen Code mit javac Graph.java
Ausgabe:
$ java Graph
* 3 * 2 * * * * 4
3 * * * * * * 4 *
* * * 6 * 1 * 2 *
2 * 6 * 1 * * * *
* * * 1 * * * * 8
* * 1 * * * 8 * *
* * * * * 8 * * *
* 4 2 * * * * * *
4 * * * 8 * * * *
ReachSet = 0 Min cost edge: (0,3)cost = 2
ReachSet = 0 3
Min cost edge: (3,4)cost = 1
ReachSet = 0 3 4
Min cost edge: (0,1)cost = 3
ReachSet = 0 1 3 4
Min cost edge: (0,8)cost = 4
ReachSet = 0 1 3 4 8
Min cost edge: (1,7)cost = 4
ReachSet = 0 1 3 4 7 8
Min cost edge: (7,2)cost = 2
ReachSet = 0 1 2 3 4 7 8
Min cost edge: (2,5)cost = 1
ReachSet = 0 1 2 3 4 5 7 8
Min cost edge: (5,6)cost = 8
ReachSet = 0 1 2 3 4 5 6 7 8
0 --> 0
0 --> 1
7 --> 2
0 --> 3
3 --> 4
2 --> 5
5 --> 6
1 --> 7
0 --> 8