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