数据结构——普里姆（Prim）算法

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。
以下是数据结构中关于普里姆算法的操作（编程风格参考严蔚敏版数据结构）。

头文件及宏

#include
#include
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100    
#define OK 1
#define ERROR -1;
typedef int status;
1
2
3
4
5
6
7
8
9
10

图以及最短边集合的声明

typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 10;
}AMGraph; 

typedef struct{
	VerTexType adjvex;//最小边在顶点集U的顶点 
	ArcType lowcost;//最小边上的权值 
}Closedge[MVNum];

1
2
3
4
5
6
7
8
9
10
11

特别说明！！！！！
在Closedge中，起点是通过节点VerTexType类型变量表示，而终点是通过下标int类型变量来表示。
adjvex就是某条边的起点，lowcost就是两点之间权值（距离）,closedge[i]里的i是终点的下标。
理解好这个很重要，如果这个理解不好，那就不知道Prim里close辅助数组是怎么用的了。

举个例子

如何算出上图里的最小生成树呢？
老样子先弄出邻接矩阵：

Prim核心算法：

void Prim(AMGraph &G,VerTexType v){
	int vi = LocateVex(G,v);//获取起始点的下标
	Closedge close;//辅助数组，用来记录不同点之间的距离以及起始位置（可理解为是一个点边集合） 
	for(int i=0;i<G.vexnum;i++){
		if(vi!=i){
			close[i].adjvex=v;
			close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点（就是假设起点到全部点的距离都是最短） 
		}else{
			close[i].lowcost = 0;
		} 
	} 
	for(int i=1;i<G.vexnum;i++){//i从1开始是因为循环不需要执行vexnum次，不必管节点到自己的距离 
		int k = Min(close,G);//获取当前点边集合里边权值最小的终点（close里下标表示终点，adjvex表示起点，lowcost表示权值） 
		VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
		VerTexType end = G.vexs[k];//当前边集合里最短边的终点
		cout<<start<<"-"<<close[k].lowcost<<"-"<<end<<endl;//输出本次找出来的最短边及端点
		for(int j=0;j<G.vexnum;j++){//更新close表 
			if(G.arcs[k][j]<close[j].lowcost){//如果end到j点的距离小于start到j点的距离 
				//这是以对象的形式简写 
				close[j] = {G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离 
				//等价于这样写
//				close[i].adjvex=G.vexs[k]; 
//				close[i].lowcost=G.arcs[k][j];
			}//if
		}//for 
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

算法执行过程（红色线表示更新的边，蓝色的表示已被选取的边，黑色的表示当前步骤未被操作的边）：

初始化辅助数组close。这一步目的是让起点直连其它的节点（就是说假设起点到其它全部节点的距离是最短的）。画出来是这样的：
此时的close记录的就是从A到其它全部节点的距离的集合。
开始第一轮循环：在close这些边里选出最短的边，AC的值最小，记录起点为A终点为C（不必做更新操作，因为这条边本就在close里）。然后以AC同时和BEFD比较距离（权值大小）。比如：A到B的距离为为6，C到B的距离是5，close里本来是A到B的边变成C到B，然后close变成如下情况：

然后AC和E比较，和F比较、和D比较，CE
第二轮循环开始：然后选出最短的那条：CF（权值为4）。此时close是这个情况:

然后A、C、F同时比较距离和B、E、D的距离。CB权值最小close不变，C和F到E距离一致，保持CE相连，FD权值比CD和AD都小，连接FD，更新close。此时的close是这样子的：

第三轮循环开始：此时的close是这样的：

A、C、F、D同时和B、E比较距离：发现是CB最短（但是在2轮循环里CB这条边已经在close里了，就没有实际更新close的操作）
第四轮循环开始：此时的close是这样的：

A、B、C、D、F同时与E比较权值：BE的距离比原先的CE短，取消CE更新为BE。此时的close是这个情况：

此时最小生成树生成完毕。最后结果如下所示：

代码执行结果：

源码

#include
#include
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100    
#define OK 1
#define ERROR -1;
typedef int status;

typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 10;
}AMGraph; 

typedef struct{
	VerTexType adjvex;//最小边在顶点集U的顶点 
	ArcType lowcost;//最小边上的权值 
}Closedge[MVNum];
//其实说白了就是adjvex就是某条边的起点，lowcost就是权值（距离）,closedge[i]的i是终点。
//理解好这个很重要。 
status CreateUDN(AMGraph &G){//创建无向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = 0;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][1]=6;G.arcs[0][2]=1;G.arcs[0][3]=5;
	G.arcs[1][2]=5;G.arcs[1][4]=3;
	G.arcs[2][3]=5;G.arcs[2][4]=6;G.arcs[2][5]=4;
	G.arcs[3][5]=2;
	G.arcs[4][5]=6;
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]!=MaxInt){
				G.arcs[j][i] = G.arcs[i][j];
			} 
		}
	}//矩阵对称 
	return OK; 
}

void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
		}
		cout<<endl;
	}
}

int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

int Min(Closedge close,AMGraph G){
	int min = MaxInt;
	int mini;
	for(int i=0;i<G.vexnum;i++){
		if(min>close[i].lowcost&&close[i].lowcost!=0){//不等于0是指不和自身比较，没意义 
			min = close[i].lowcost;
			mini = i; 
		}
	}
//	cout<
	return mini;
} 

void Prim(AMGraph &G,VerTexType v){
	int vi = LocateVex(G,v);//获取起始点的下标
	Closedge close;//辅助数组，用来记录不同点之间的距离以及起始位置（可理解为是一个点边集合） 
	for(int i=0;i<G.vexnum;i++){
		if(vi!=i){
			close[i].adjvex=v;
			close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点（就是假设起点到全部点的距离都是最短） 
		}else{
			close[i].lowcost = 0;//0表示自身或该边已被选取。 
		} 
	} 
	for(int i=1;i<G.vexnum;i++){//i从1开始是因为循环不需要执行vexnum次，不必管节点到自己的距离 
		int k = Min(close,G);//获取当前点边集合里边权值最小的终点（close里下标表示终点，adjvex表示起点，lowcost表示权值） 
		VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
		VerTexType end = G.vexs[k];//当前边集合里最短边的终点
		cout<<start<<"-"<<close[k].lowcost<<"-"<<end<<endl;//输出本次找出来的最短边及端点
		for(int j=0;j<G.vexnum;j++){//更新close表 
			if(G.arcs[k][j]<close[j].lowcost){//如果end到j点的距离小于start到j点的距离 
				//这是以对象的形式简写 
				close[j] = {G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离 
				//等价于这样写
//				close[i].adjvex=G.vexs[k]; 
//				close[i].lowcost=G.arcs[k][j];
			}//if
		}//for 
	} 
}

int main(){
	AMGraph G;
	CreateUDN(G);
	ShowGraph(G);
	Prim(G,'A'); 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

关于时间复杂度和空间复杂度

设顶点数n，边数e。邻接矩阵:O(n^2) 邻接表:O(elogn)

敬请批评指正。