algorithm
Prim's algoritm
Sök…
Introduktion till Prim's algoritm
Låt oss säga att vi har 8 hus. Vi vill ställa in telefonlinjer mellan dessa hus. Kanten mellan husen representerar kostnaden för att ställa in linjen mellan två hus.
Vår uppgift är att sätta upp linjer på ett sådant sätt att alla hus är anslutna och kostnaden för att sätta upp hela anslutningen är minimal. Hur hittar vi det nu? Vi kan använda Prims algoritm .
Prim's Algoritm är en girig algoritm som hittar ett minimum sträckande träd för en viktad, riktad graf. Detta betyder att den hittar en delmängd av kanterna som bildar ett träd som inkluderar varje nod, där den totala vikten av alla kanter i trädet minimeras. Algoritmen utvecklades 1930 av den tjeckiska matematikern Vojtěch Jarník och återupptäcktes och publicerades senare av datorforskaren Robert Clay Prim 1957 och Edsger Wybe Dijkstra 1959. Den är också känd som DJP-algoritm , Jarniks algoritm , Prim-Jarnik algoritm eller Prim-Dijsktra algoritm .
Låt oss nu titta på de tekniska termerna först. Om vi skapar ett diagram, S med hjälp av vissa noder och kanter på en inriktad graf G , kallas S en undergraf av diagrammet G. Nu kommer S att kallas ett Spanning Tree om och bara om:
- Den innehåller alla noderna i G.
- Det är ett träd, det betyder att det inte finns någon cykel och alla noder är anslutna.
- Det finns (n-1) kanter i trädet, där n är antalet noder i G.
Det kan finnas många Spanning Tree i en graf. Minsta spännträdet på ett viktat, underriktat diagram är ett träd, så att summan av kanternas vikt är minimal. Nu kommer vi att använda Prims algoritm för att ta reda på det minsta spännträdet, det är hur man sätter upp telefonlinjerna i vårt exempelgraf på så sätt att kostnaden för installationen är minimal.
Först väljer vi en källnod. Låt oss säga, nod-1 är vår källa . Nu lägger vi till kanten från nod-1 som har minimikostnaden för vår undergraf. Här markerar vi kanterna i subgrafen med färgen blå . Här är 1-5 vår önskade kant. 
Nu överväger vi alla kanter från nod-1 och nod-5 och tar det minsta. Eftersom 1-5 redan är markerat tar vi 1-2 . 
Den här gången överväger vi nod-1 , nod-2 och nod-5 och tar minimikanten som är 5-4 . 
Nästa steg är viktigt. Från nod-1 , nod-2 , nod-5 och nod-4 är minimikanten 2-4 . Men om vi väljer den, kommer det att skapa en cykel i vår undergraf. Detta beror på att nod-2 och nod-4 redan finns i vår undergraf. Så att ta fördel av 2-4 gynnar oss inte. Vi väljer kanterna på ett sådant sätt att det lägger till en ny nod i vår undergraf . Så vi väljer kant 4-8 . 
Om vi fortsätter på detta sätt väljer vi kant 8-6 , 6-7 och 4-3 . Vår undergraf ser ut som: 
Detta är vår önskade subgraf, som ger oss det lägsta spännträdet. Om vi tar bort kanterna som vi inte valde får vi: 
Detta är vårt minimum spanning tree (MST). Så kostnaden för att konfigurera telefonanslutningarna är: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . Och uppsättningen av hus och deras anslutningar visas i diagrammet. Det kan finnas flera MST för en graf. Det beror på källoden vi väljer.
Pseudokoden för algoritmen anges nedan:
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
Komplexitet:
Tidskomplexiteten hos ovanstående naiva metod är O (V²) . Den använder adjacency matrix. Vi kan minska komplexiteten med hjälp av prioriteringskön. När vi lägger till en ny nod i Vnew kan vi lägga till dess angränsande kanter i prioriteringskön. Släpp sedan den minsta viktade kanten från den. Då blir komplexiteten: O (ElogE) , där E är antalet kanter. Återigen kan en Binary Heap konstrueras för att minska komplexiteten till O (ElogV) .
Pseudokoden med Prioritetskö ges nedan:
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
Här lagrar nyckel [] minimikostnaden för korsning av nod-v . överordnad [] används för att lagra överordnad nod. Det är användbart för att korsa och skriva ut trädet.
Nedan är ett enkelt program i 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();
}
}
Kompilera ovanstående kod med javac Graph.java
Produktion:
$ 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