图的最小生成树-Prim算法

思想：

  • 将图中的顶点分成两类：树顶点和非树顶点
  1. 首先选择一个顶点加入生成树
  2. 枚举树顶点的所有出边，看看哪些边可以连接到非树顶点，并且边越短越好
  3. 连接非树顶点，重复步骤直到n个顶点全都加到生成树中
  • 在步骤2中，枚举所有出边是比较费时的，可以利用Dijkstra最短路径算法的思想，利用一个dis数组记录各个顶点到源点的距离，每次往生成树加入点后看看这个点能否使非树顶点到生成树的距离变短

镖局问题Prim算法版本

整体代码

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
#include<iostream>
using namespace std;

int main()
{
	int point,edge;//点数和边数
	int minl = 0;//记录总和
	int inf = 999999;//设置无穷大
	cin >> point >> edge;

	int** arr = new int*[point + 1];
	for (int i = 0; i <= point; i++)
	{
		arr[i] = new int[point + 1];
		for (int j = 0; j <= point; j++)
		{
			arr[i][j] = inf;
		}
		arr[i][i] = 0;
	}//初始化邻接矩阵

	int a, b, c;
	for (int i = 0; i < edge; i++)
	{
		cin >> a >> b >> c;
		arr[a][b] = c;
		arr[b][a] = c;
	}//录入边的数据

	int* dis = new int[point + 1];
	bool* book = new bool[point + 1];
	for (int i = 1; i <= point; i++)
	{
		book[i] = false;
		dis[i] = arr[1][i];
	}//初始化book数组和dis数组

	//算法核心部分
	int minleng,minpoin;//记录树外的点到生成树的最短距离、该点的编号
	int count = 0;//记录生成树中已有顶点数
	book[1] = true;//一号顶点先开始
	count++;
	while (count < point)
	{
		minleng = inf;
		for (int i = 1; i <= point; i++)//循环查找，更新最小值和点
		{
			if (book[i] == false && dis[i] < minleng)
			{
				minleng = dis[i];
				minpoin = i;
			}
		}

		book[minpoin] = true;//找到最小值的点,标记
		count++;//次数增加
		minl += minleng;//权增加

		for (int i = 1; i <= point; i++)//更新距离数组
		{
			//如果某个点还没有在生成树里
			//且通过刚刚加进来的点，可以使非树顶点到生成树距离变短
			if (book[i] == false && dis[i] > arr[minpoin][i])
			{
				dis[i] = arr[minpoin][i];
				//那么更新距离
			}
		}
        
        //重复添加顶点直到所有顶点都被添加进来
	}

	cout << minl;

	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
//算法核心部分
int minleng,minpoin;//记录树外的点到生成树的最短距离、该点的编号
int count = 0;//记录生成树中已有顶点数
book[1] = true;//一号顶点先开始
count++;

while (count < point)
{
	minleng = inf;
	for (int i = 1; i <= point; i++)//循环查找，更新最小值和点
	{
		if (book[i] == false && dis[i] < minleng)
		{
			minleng = dis[i];
			minpoin = i;
		}
	}

	book[minpoin] = true;//找到最小值的点,标记
	count++;//次数增加
	minl += minleng;//权增加

	for (int i = 1; i <= point; i++)//更新距离数组
	{
		//如果某个点还没有在生成树里
		//且通过刚刚加进来的点，可以使到生成树距离变短
		if (book[i] == false && dis[i] > arr[minpoin][i])
		{
			dis[i] = arr[minpoin][i];
			//那么更新距离
		}
	}

}

两种最短路径算法

  • Kruskal算法适用于稀疏图

  • Prim算法适用于稠密图，使用了堆优化的Prim算法适用于稠密图