algorithm
Prim's algoritme
Zoeken…
Inleiding tot het algoritme van Prim
Laten we zeggen dat we 8 huizen hebben. We willen telefoonlijnen tussen deze huizen opzetten. De rand tussen de huizen vertegenwoordigt de kosten van het zetten van een lijn tussen twee huizen.
Onze taak is om lijnen zo in te stellen dat alle huizen verbonden zijn en de kosten voor het opzetten van de hele verbinding minimaal zijn. Hoe komen we daar nu achter? We kunnen het algoritme van Prim gebruiken.
Prim's algoritme is een hebzuchtig algoritme dat een minimale overspanningboom vindt voor een gewogen ongerichte grafiek. Dit betekent dat het een subset van de randen vindt die een boom vormt die elk knooppunt omvat, waarbij het totale gewicht van alle randen in de boom wordt geminimaliseerd. Het algoritme werd in 1930 ontwikkeld door de Tsjechische wiskundige Vojtěch Jarník en later herontdekt en opnieuw gepubliceerd door computerwetenschapper Robert Clay Prim in 1957 en Edsger Wybe Dijkstra in 1959. Het is ook bekend als DJP-algoritme , Jarnik's algoritme , Prim-Jarnik-algoritme of Prim-Dijsktra algoritme .
Laten we nu eerst de technische termen bekijken. Als we een grafiek maken, S met behulp van enkele knooppunten en randen van een niet-gerichte grafiek G , dan wordt S een subgraaf van de grafiek G genoemd . Nu wordt S een Spanning Tree genoemd als en alleen als:
- Het bevat alle knooppunten van G.
- Het is een boom, wat betekent dat er geen cyclus is en alle knooppunten zijn verbonden.
- Er zijn (n-1) randen in de boom, waarbij n het aantal knooppunten in G is .
Er kunnen veel Spanning Tree 's van een grafiek zijn. De minimale spanboom van een gewogen ongerichte grafiek is een boom, zodat de som van het gewicht van de randen minimaal is. Nu zullen we het algoritme van Prim gebruiken om de minimale overspanningboom te vinden, dat is hoe we de telefoonlijnen in onze voorbeeldgrafiek zodanig kunnen instellen dat de installatiekosten minimaal zijn.
In eerste instantie zullen we een bron knooppunt te selecteren. Laten we zeggen dat knooppunt-1 onze bron is . Nu voegen we de rand van knooppunt-1 met de minimale kosten toe aan onze subafbeelding. Hier markeren we de randen in de subafbeelding met de kleur blauw . Hier is 1-5 onze gewenste voorsprong. 
Nu beschouwen we alle randen van knooppunt-1 en knooppunt-5 en nemen het minimum. Omdat 1-5 al is gemarkeerd, nemen we 1-2 . 
Deze keer beschouwen we knooppunt-1 , knooppunt-2 en knooppunt-5 en nemen de minimale rand die 5-4 is . 
De volgende stap is belangrijk. Van knooppunt-1 , knooppunt-2 , knooppunt-5 en knooppunt-4 is de minimale rand 2-4 . Maar als we die selecteren, wordt er een cyclus in onze subafbeelding gemaakt. Dit komt omdat knooppunt-2 en knooppunt-4 al in onze subafbeelding staan. Dus voordeel halen voor 2-4 komt ons niet ten goede. We zullen de randen zodanig selecteren dat een nieuwe knoop in onze subafbeelding wordt toegevoegd . Dus selecteren we rand 4-8 . 
Als we op deze manier doorgaan, selecteren we rand 8-6 , 6-7 en 4-3 . Onze subfoto ziet eruit als: 
Dit is onze gewenste subfoto, die ons de minimale overspannende boom geeft. Als we de randen verwijderen die we niet hebben geselecteerd, krijgen we: 
Dit is onze minimum spanning tree (MST). De kosten voor het opzetten van de telefoonverbindingen zijn dus: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . En de set huizen en hun verbindingen worden getoond in de grafiek. Er kunnen meerdere MST van een grafiek zijn. Het hangt af van de bron knooppunt we kiezen.
De pseudo-code van het algoritme wordt hieronder gegeven:
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
complexiteit:
Tijdcomplexiteit van de bovenstaande naïeve benadering is O (V²) . Het maakt gebruik van aangrenzende matrix. We kunnen de complexiteit verminderen met behulp van prioriteitswachtrij. Wanneer we een nieuw knooppunt aan Vnew toevoegen , kunnen we de aangrenzende randen ervan in de prioriteitswachtrij toevoegen. Haal vervolgens de minimaal gewogen rand eruit. Dan is de complexiteit: O (ElogE) , waarbij E het aantal randen is. Wederom kan een binaire hoop worden geconstrueerd om de complexiteit tot O (ElogV) te verminderen .
De pseudo-code met behulp van Priority Queue wordt hieronder gegeven:
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 slaat sleutel [] de minimumkosten op voor het doorlopen van knooppunt-v . bovenliggende [] wordt gebruikt om het bovenliggende knooppunt op te slaan. Het is handig voor het doorlopen en afdrukken van de boom.
Hieronder staat een eenvoudig programma op 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();
}
}
Compileer de bovenstaande code met javac Graph.java
Output:
$ 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