Prims 演算法簡介
假設我們有 8 所房子。我們想在這些房屋之間設定電話線。房屋之間的邊緣代表兩間房屋之間的線路設定成本。
我們的任務是以所有房屋都連線起來的方式設定線路，並且建立整個連線的成本最低。現在我們如何找到它？我們可以使用 Prim 的演算法。
Prim 演算法是一種貪心演算法，可以為加權無向圖找到最小生成樹。這意味著它找到形成包含每個節點的樹的邊的子集，其中樹中所有邊的總權重被最小化。該演算法由捷克數學家 VojtěchJarník於 1930 年開發，後來由電腦科學家 Robert Clay Prim於 1957 年和 Edsger Wybe Dijkstra於 1959 年重新發布和重新發表。它也被稱為 DJP 演算法， Jarnik 演算法， Prim-Jarnik 演算法或 Prim-Dijsktra 演算法。
現在讓我們先看一下技術術語。如果我們建立的曲線圖，S使用一些節點和無向圖的邊緣 ģ ，然後S被稱為子圖的曲線圖的 G ^ 。現在 S 將被稱為**生成樹，**當且僅當：
- 它包含 G 的所有節點。
- 它是一棵樹，這意味著沒有迴圈，所有節點都連線在一起。
- 樹中有 （n-1）個邊，其中 n 是 G 中的節點數。
可以有許多生成樹的圖形。加權無向圖的最小生成樹是樹，使得邊的權重之和最小。現在我們將使用 Prim 演算法找出最小生成樹，即如何在設定圖中設定電話線，使設定成本最小。
首先，我們將選擇一個源節點。比方說， node-1 是我們的來源。現在我們將從節點 1 新增具有最低成本的邊緣到子圖。在這裡，我們使用藍色標記子圖中的邊。 1-5 這是我們理想的優勢。 
現在我們考慮 node-1 和 node-5 的所有邊緣並採用最小值。由於 1-5 已經標記，我們採取 1-2 。 
這次，我們考慮 node-1 ， node-2 和 **node-5，**並取最小邊緣 5-4 。 
下一步很重要。從 node-1 ， node-2 ， node-5 和 node-4 ，最小邊緣為 2-4 。但是如果我們選擇那個，它將在我們的子圖中建立一個迴圈。這是因為 node-2 和 node-4 已經在我們的子圖中。所以取得優勢 2-4 對我們沒有好處。我們將選擇邊緣，使其在子圖中新增新節點。所以我們選擇 4-8 邊。 
如果我們繼續這樣，我們將選擇邊緣 8-6 ， 6-7 和 4-3 。我們的子圖將如下所示： 
這是我們想要的子圖，它將為我們提供最小的生成樹。如果我們刪除了未選擇的邊緣，我們將得到： 
這是我們的最小生成樹 （MST）。因此，建立電話連線的成本是： 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 。房屋及其連線的集合顯示在圖表中。圖表可以有多個 MST 。這取決於我們選擇的源節點。
演算法的虛擬碼如下：
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
複雜：
上述天真方法的時間複雜度為 O（V²） 。它使用鄰接矩陣。我們可以使用優先順序佇列來降低複雜性。當我們向 Vnew 新增一個新節點時，我們可以在優先順序佇列中新增它的相鄰邊。然後從中彈出最小加權邊。然後複雜性將是： O(ElogE) ，其中 E 是邊數。同樣可以構造二元堆以降低 O(ElogV) 的複雜性。
使用優先順序佇列的虛擬碼如下：
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
這裡 key [] 儲存遍歷 node-v 的最小成本。 parent [] 用於儲存父節點。它對於遍歷和列印樹很有用。
下面是 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();
}
}
使用 javac Graph.java 編譯上面的程式碼
輸出：
$ 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