学步园

Prim算法

涉及到的几个基础知识

• 生成树： 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含途中所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个声称森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。

• 图的遍历： 和树的遍历相似，若从图中某顶点出发，访问遍途中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的常用遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS），对每种搜索顺序，访问各顶点的顺序也不是唯一的。
• 在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G'，称作图G的生成树。一个图可以有多个生成树，从不同的顶点除法，采用不同的遍历顺序，遍历时所经过的边也就不同。
• 最小生成树：在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树成为图的最小生成树（MST）。
• MST性质：MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。

Prim算法

• 基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：

• 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
  此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

• Prim算法的核心:始终保持TE中的边集构成一棵生成树。

• Prim算法举例：

采用的是顶点数为6的无向连通图：

设集合V={A,B,C,D,E,F}，即所有顶点的集合。

集合U为最小生成树的结点。

按照Prim算法：

1. 将A加入U，此时，U={ A }，V-U={ B，C，D，E}；
2. 与A邻接的顶点有B，C，D。（A，B）、（A，C）、（A，D），权值分别为6、1、5，因而选定（A，C）为最小生成树的一条边；
3. 将上一步选定的在V-U中的顶点C加入U，此时，U={A，C}， V-U={ B，D，E，F}；
4. V-U中与U中顶点组成的边有（A，B）、（A，D）、（C，B）、（C，D）、（C，E）、（C，F），权值分别为6、5、5、5、6、4，因而选定（C，F）为最小生成树的一条边；
5. 将F加入U中，此时U={ A，C，F} ， V-U={ B， D，E}；
6. V-U中与U中顶点组成的边有（A，B）、（A，D）、（C，B）、（C，D）、（C，E）、（F，D）、（F，E），权值分别为6、5、5、5、6、2、6，选定（F，D）为最小生成树的一条边；
7. 将D加入U中，此时，U={ A，C，F，D}， V-U={ B，E}；
8. V-U中与U中顶点组成的边有（A，B）、（C，B）、（C，E）、（F，E），权值分别为6、5、6、6，选定（C，B）为最小生成树的一条边。
9. 将B加入U中，此时U= {A，C，F ，D，B }, V -U={E };
10. V-U中与U中顶点组成的边有（B，E）、（C，E）、（F，E），权值分别为3、6、6，选定（B，E）为最小生成树的一条边。
11. 将E加入U中，此时U={A ，C，F，D，B，E}，完成MST的生成。

其生成过程图示如下：

Prim算法C代码

/* 求最小生成树的prim算法 */

#include <stdio.h>
#include <string.h>

#define MaxSize 20
#define MAX 10000

typedef char VertexType;

//定义图 的邻接矩阵表示法结构
typedef struct Graph {
	VertexType ver[MaxSize+1];
	int edg[MaxSize][MaxSize];
}Graph;

//邻接矩阵法图的生成函数
void CreateGraph( Graph *g )
{
	int i = 0;
	int j = 0;
	int VertexNum;
	VertexType Ver;

	printf("请输入图的顶点:\n");
	while( '\n' != (Ver=getchar()) )
		g->ver[i++] = Ver;
	g->ver[i] = '\0';

	VertexNum = strlen(g->ver);
	printf("请输入相应的的邻接矩阵:\n");
	for( i=0; i<VertexNum; i++ )
		for( j=0; j<VertexNum; j++ )
			scanf("%d", &g->edg[i][j]);
}

//打印图的结点标识符和邻接矩阵
void PrintGraph( Graph g )
{
	int i, j;
	int VertexNum = strlen(g.ver);
	printf("图的顶点为:\n");
	for( i=0; i<VertexNum; i++ )
		printf("%c ", g.ver[i]);
	printf("\n");

	printf("图的邻接矩阵为:\n");
	for( i=0; i<VertexNum; i++ ) {
		for( j=0; j<VertexNum; j++ )
			printf("%d ", g.edg[i][j]);
		printf("\n");
	}
}

//求图的顶点数
int CalVerNum( Graph g )
{
	return strlen(g.ver);
}

//将不邻接的顶点之间的权值设置为MAX
void SetWeight( Graph *g )
{
	for( int i=0; i<CalVerNum(*g); i++ )
		for( int j=0; j<CalVerNum(*g); j++ )
			if( 0 == g->edg[i][j] )
				g->edg[i][j] = MAX;
}

//运用prim算法求最小生成树
void prim( Graph g, int VerNum, int *parent )
{
	int i, j, k;
	int lowcost[MaxSize];
	int closest[MaxSize], used[MaxSize];
	int min;

	for( i=0; i<VerNum; i++ ) {			//对辅助数组lowcost和closest进行初始化
		lowcost[i] = g.edg[0][i];
		closest[i] = 0;
		used[i] = 0;					//used[i] == 0 表示i顶点在U中，反之，在V-U中。
		parent[i] = -1;
	}

	used[0] = 1;						//第一步将编号为0的顶点放入U中，也可以是其他顶点

	for( i=0; i<VerNum-1; i++ ) {
		j = 0;
		min = MAX;

		for( k=1; k<VerNum; k++ )		//找到V-U中的与U中顶点组成的最小权值的边的顶点编号
			if( (0==used[k]) && (lowcost[k]<min) ) {
				min = lowcost[k];
				j = k;
			}

		parent[j] = closest[j];

		used[j] = 1;					//将j顶点加入U中

		for( k=0; k<VerNum; k++ )		//由于j顶点加入U中，更新lowcost和closest数组中的元素，检测V-U中的顶点到j顶点的权值是否比j加入U之前的lowcost数组的元素小
			if( (0==used[k]) && (g.edg[k][j]<lowcost[k]) ) {
				lowcost[k] = g.edg[k][j];
				closest[k] = j;			//closest数组保存的是U中到V-U中最小权值的顶点编号
			}
	}
}

//打印最小生成树的边和MST的权值
void PrintMST( Graph g, int *parent )
{
	int VerNum = CalVerNum( g );
	int weight = 0;
	printf("MST的边为:\n");
	for( int i=1; i<VerNum; i++ ) {		 //VerNum-1条边
		printf("%c--%c\n", g.ver[parent[i]], g.ver[i] );
		weight+=g.edg[parent[i]][i];
	}
	printf("MST的权值为:%d\n", weight);
}


int main()
{
	Graph g;
	int parent[20];

	CreateGraph ( &g );
	PrintGraph( g );
	
	SetWeight( &g );

	prim( g, CalVerNum(g), parent );
	PrintMST( g, parent );

	return 0;
}

测试结果：

数据即为前面所讲的图。