最小生成树（MST）之Prim算法

首先，让我们了解最小生成树（Maximal Spanning Tree,  MST）问题。

Problem: 给定无向带权图G=(V,E)，其点集为V，边集为E。要求选出边集E的一个子集E‘，使得E'能够让所有点连通且边权和最小。

由于给定无向图G,连接G中所有点，且边集是E的子集的树称为G的生成树（Spanning Tree），而权值最小的生成树称为最小生成树，该问题即是让我们求出G的最小生成树。

下面给出求解最小生成树的Prim算法的表述：

（1）取一新点集T = { v0 }，v0为V中任意一点，此时 V-T = V- { v0 }。

（2）始终进行（2）这一步骤直到T = V：对于所有满足如下条件的边e：e的一个端点在T中，另一个端点在V-T中。找出其中权值最小的边，将其不在T中的端点加入T。

注：Prim算法的正确性在此我不去证明，请读者自行证明或查阅资料，提示Prim算法含有贪心思想。

下面给出Prim算法的实现代码，并将对其进行优化（假定图G的边权值在邻接矩阵dis[][]中给出，dis[i][j]为-1时表示点i与j之间不存在边，否则表示点i与j之间的边权值）：

（1）朴素的Prim算法：

这里只给出伪代码：

T = { v0 } 	// v0 is an arbitary point in V
for k from 1 to |V|-1	// we need to add |V|-1 points to T and then T==V
  search all edges for the shortest whose one endpoint is in T, let the edge you find named 'e'
  add e to T
           

朴素的算法实现效率较低，下面来看另一种实现方法，效率为O(n^2)。

（2）另一种更好的实现方法：

代码中min_dis数组存放各个顶点到T集合的最小距离（即到T中各点的距离中最小的一个），nearest_v存放对于程序运行中未放入T中的各个顶点，距离其最近的T中顶点序号（该数组用于打印MST），N=|V|。

实现代码如下：

#define Distance double
#define INF 1000000
#define MAXN 100
double x[MAXN],y[MAXN];
Distance dis[MAXN][MAXN];
Distance min_dis[MAXN];
//int nearest_v[MAXN];

Distance Prim(int v0, int N)
{
	//init
	for(int i=0; i<N; i++)
	{
		min_dis[i] = dis[i][v0];
//		nearest_v[i] = v0;
	}
	min_dis[v0] = 0;	
	Distance total_dis = 0;	//生成树所有边权之和
	for(int k=1; k<N; k++)
	{
		Distance md = INF;	//min_dis中的最小值
		int nv = v0;	//nv是min_dis中最小者的序号，意为距离T最近的顶点，初始化为v0（其实不初始化也没关系好像~）
		for(int i=0; i<N; i++) if(min_dis[i]!=0)
		{
			if(md > min_dis[i]) 
			{
				md = min_dis[i];
				nv = i;
			}
		}
		//将nv加入T
		total_dis += md;
		min_dis[nv] = 0;
		//更新min_dis及nearest_v
		for(int i=0; i<N; i++) if(min_dis[i]!=0)
		{
			if(min_dis[i] > dis[i][nv])
			{
				min_dis[i] = dis[i][nv];
//				nearest_v[i] = nv;
			}
		}
	}
	return total_dis;
}
           

至此，Prim算法的讲解结束。如有错误或其他优化，欢迎大家批评指正（= @ =）。

另外，附上一道Prim算法的练习题，虽然不可以直接套用模板，但这样不是更有助理解Prim算法么(>^ω^<)？

练习：UVaOJ 10397: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1338

题解参见我的博客文章：UVa 10397： Connect the Campus