使用Prim算法得到生成最小生成树的总权值_计算最小生成树的权值

Prim 算法

Prim算法简介

Prim算法是一种贪心算法，主要用于解决最小生成树的构建问题。最小生成树是在一个有向或无向图中，边权值总和最小的生成树。Prim算法从图中的一个顶点出发，逐步扩展生成树，直到包含所有顶点为止。该算法以最小化生成树上的边权值总和为目标，因此得名“最小生成树”（Minimum Spanning Tree，简称MST）123。

Prim算法的工作原理

Prim算法的核心思想是从一个顶点开始，逐步扩展生成树，直到包含所有顶点为止。具体实现过程如下：

1. 初始化一个空的生成树，选择一个起始顶点；
2. 将所有与当前最小生成树集合中的顶点相连的边加入到优先队列中；
3. 从优先队列中取出权值最小的边（即堆顶元素），如果这条边连接的顶点不在最小生成树集合中，则将该顶点和边加入到最小生成树中，并将这条边的所有相邻边加入到优先队列中；
4. 重复步骤3，直到所有顶点都被加入到最小生成树中。

求达到最小生成树所需的总权值问题

例如根据这张图片，按照上面讲述的算法思路。

我们从结点0开始生成树，

连通分量如目前生成树包含的结点

第一步：
连通分量：结点0
路径优先队列：0->1,0->2,0->3
得到最短路径为0->2，权值为1

第二步：
连通分量：结点0，结点2
路径优先队列：0->1,0->3,2->1,2->3,2->4,2->5
得到最短路径为2->5，权值为4

第三步：
连通分量：结点0，结点2，结点5
路径优先队列：0->1,0->3,2->1,2->3,2->4,5->3
得到最短路径为5->3，权值为2

依次类推。

初始化图结构

根据图片构造图的邻接矩阵为：

int g[6][6];     //图的邻接矩阵 
void newGraph() {
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			g[i][j] = INT32_MAX;
		}
	}
	g[0][1] = 6;
	g[0][2] = 1;
	g[0][3] = 5;
	g[1][2] = 5;
	g[1][4] = 3;
	g[2][3] = 7;
	g[2][4] = 5;
	g[2][5] = 4;
	g[3][5] = 2;
	g[4][5] = 6;
	g[0][1] = 6;
	g[2][0] = 1;
	g[3][0] = 5;
	g[3][2] = 5;
	g[4][2] = 3;
	g[3][2] = 7;
	g[4][1] = 3;
	g[4][2] = 5;
	g[5][2] = 4;
	g[5][3] = 2;
	g[5][4] = 6;
	for (int i = 0; i < 6; i++) {      //这里是展示邻接矩阵的权值
		for (int j = 0; j < 6; j++) {
			cout << g[i][j] << " ";
		}
		cout << endl;
	}
}
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

运行结果如下

说明构造出来的没错。

现在就需要构造优先队列，以及构成优先队列的元素：路径

vector<int> ans; //来记录已连通的结点
int Path_sum;        //记录总路径值

//检测是否重复的函数
bool repeatGraph(int j) {   //传入路径的终点 
	for (int i : ans) {     //如果这个终点包含在已选中的路径那
		if (i == j) return false;    //重复返回false值 
	}
	return true;            //否则返回true 
}
void Prim(int v) {
	ans.push_back(v);       //将选择的结点添加到连通分量中 
	if (ans.size() == 6) return;          //递归终止条件：连通分量的结点数量达到6 

	int node;          //记录最短路径所连接的结点
	int min_path = INT32_MAX;      //存放最短的路径权值，且初始化最大值 
	
	queue<Path> temp_path;
	//构造路径优先队列 
	for(int i : ans) {
		for(int j = 0; j < 6; j++) {
				Path path;
			if(g[i][j] != INT32_MAX){       //该路径存在时 
				path.start = i;             //获取路径的起点 
				path.terminal = j;          //获取路径的终点 
				path.values = g[i][j];      //获取路径的权值 
				temp_path.push(path);       //将路径加入优先队列中 
			}
		}
	} 
	while(!temp_path.empty()){               //循环条件时队列不为空 
		 Path path = temp_path.front();      //获取队首元素 
		 if(path.values < min_path && repeatGraph(path.terminal)) {   //当满足找到更短路径并且该路径结点还未包含时 
		 	node = path.terminal;            //更新node值 
		 	min_path = path.values;          //更新最短路径权值 
		 }
		 temp_path.pop();                    //将该路径退出 
	}
	Path_sum += min_path;
	Prim(node);
}


int main() {
	//初始化图结构 
	newGraph();
	//从结点0开始构建最小生成树 
	Kruskal(0);  
	//打印出生成最小生成树所需的代价（总权值） 
	cout << "cost of minimum spanning tree is :" << Path_sum;
}
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

得到生成的最小生成树的总权值为15.

可以在递归中加入显示当前ans数组的结点，得到最小生成树的过程，如

	for(int i : ans) {
		cout << i << " -> ";
	} 
	cout << "null" <<endl;
	
1
2
3
4
5

可以看到代码生成的过程并没有问题.