algorithm
Algorytm Prim
Szukaj…
Wprowadzenie do algorytmu Prim
Załóżmy, że mamy 8 domów. Chcemy ustawić linie telefoniczne między tymi domami. Krawędź między domami reprezentuje koszt ustawienia linii między dwoma domami.
Naszym zadaniem jest takie ustawienie linii, aby wszystkie domy były połączone, a koszt założenia całego połączenia jest minimalny. Jak się tego dowiemy? Możemy użyć algorytmu Prim .
Algorytm Prim jest algorytmem zachłannym, który znajduje minimalne drzewo rozpinające dla ważonego niekierowanego wykresu. Oznacza to, że znajduje podzbiór krawędzi, który tworzy drzewo, które obejmuje każdy węzeł, w którym całkowita waga wszystkich krawędzi w drzewie jest zminimalizowana. Algorytm został opracowany w 1930 r. Przez czeskiego matematyka Vojtěcha Jarníka, a następnie ponownie odkryty i ponownie opublikowany przez informatyka Roberta Claya Prim w 1957 r. I Edsger Wybe Dijkstra w 1959 r. Jest również znany jako algorytm DJP, algorytm Jarnika, algorytm Prim-Jarnik lub Prim-Dijsktra algorytm .
Teraz spójrzmy najpierw na warunki techniczne. Jeśli tworzymy wykres, S przy użyciu niektórych węzłów i krawędzi niekierowanego wykresu G , wówczas S jest nazywany podgrafsem wykresu G. Teraz S będzie nazywane drzewem opinającym, jeśli i tylko wtedy, gdy:
- Zawiera wszystkie węzły G.
- Jest to drzewo, co oznacza, że nie ma cyklu i wszystkie węzły są połączone.
- Drzewo ma (n-1) krawędzie, gdzie n jest liczbą węzłów w G.
Na wykresie może znajdować się wiele drzew opinających . Minimalne drzewo opinające nieważonego wykresu ważonego jest drzewem, tak że suma ciężaru krawędzi jest minimalna. Teraz użyjemy algorytmu Prim, aby znaleźć minimalne drzewo opinające, czyli jak skonfigurować linie telefoniczne na naszym przykładowym wykresie w taki sposób, aby koszt instalacji był minimalny.
Najpierw wybieramy węzeł źródłowy . Powiedzmy, że węzeł-1 jest naszym źródłem . Teraz dodamy krawędź z węzła-1, która ma minimalny koszt do naszego podsgrafu. Tutaj zaznaczamy krawędzie znajdujące się w podrozdziale za pomocą koloru niebieskiego . Tutaj 1-5 jest naszą pożądaną przewagą. 
Teraz bierzemy pod uwagę wszystkie krawędzie z węzła-1 i węzła-5 i przyjmujemy minimum. Ponieważ 1-5 jest już zaznaczone, bierzemy 1-2 . 
Tym razem rozważamy węzeł-1 , węzeł-2 i węzeł-5 i przyjmujemy minimalną krawędź, która wynosi 5-4 . 
Następny krok jest ważny. Z węzła-1 , węzła-2 , węzła-5 i węzła-4 minimalna krawędź wynosi 2-4 . Ale jeśli wybierzemy ten, stworzy on cykl w naszym podgrafie. Jest tak, ponieważ węzeł-2 i węzeł-4 są już w naszym podrozdziale. Zatem przewaga 2-4 nie przynosi nam korzyści. Wybramy krawędzie w taki sposób, że doda nowy węzeł w naszym podrozdziale . Wybieramy więc krawędź 4-8 . 
Jeśli będziemy kontynuować w ten sposób, wybierzemy krawędzie 8-6 , 6-7 i 4-3 . Nasz subgraf będzie wyglądał następująco: 
To jest nasz pożądany wykres podrzędny, który da nam minimalne drzewo rozpinające. Jeśli usuniemy krawędzie, których nie wybraliśmy, otrzymamy: 
To jest nasze minimalne drzewo rozpinające (MST). Koszt zestawienia połączeń telefonicznych wynosi: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . Zestaw domów i ich połączenia pokazano na wykresie. Wykres może zawierać wiele MST . To zależy od wybranego przez nas węzła źródłowego .
Pseudo-kod algorytmu podano poniżej:
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
Złożoność:
Złożoność czasowa powyższego naiwnego podejścia wynosi O (V²) . Wykorzystuje macierz przylegania. Możemy zmniejszyć złożoność za pomocą kolejki priorytetowej. Kiedy dodamy nowy węzeł do Vnew , możemy dodać jego sąsiednie krawędzie w kolejce priorytetowej. Następnie wystrzel z niego minimalną ważoną krawędź. Wtedy złożoność będzie wynosić: O (ElogE) , gdzie E jest liczbą krawędzi. Znów można zbudować Binary Heap, aby zredukować złożoność do O (ElogV) .
Pseudokod używający kolejki priorytetowej podano poniżej:
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
Tutaj klawisz [] przechowuje minimalny koszt przejścia przez węzeł-v . Parent [] służy do przechowywania węzła nadrzędnego. Jest to przydatne do przejścia i drukowania drzewa.
Poniżej znajduje się prosty program w Javie:
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();
}
}
Skompiluj powyższy kod, używając javac Graph.java
Wynik:
$ 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