生成树：如果对于图 G 中任意两个顶点 vi、vj 都是连通的，就称 G 是连通图。生成树是针对连通图而言的，是连通图的极小连通子图，它包含图中所有顶点，有且仅有 n-1 条边。

最小生成树：在图论里，树常被定义成一个无回路的连通图，起点和终点相同的路径称为回路。对于一个带权的无向连通图，它的每个生成树所有边上权值之和可能都不一样，我们把所有边上权值之和最小的那个生成树，称为这张图的最小生成树。

我们举个例子。把下图里的 6 个顶点当做 6 个房子，顶点之间边的权重当做房子和房子之间的距离。现在要在这 6 个房子之间铺设天然气管道，注意管道只要覆盖这 6 个房子就行，也就是说 6 个顶点只需要 N-1=5 条边就够了。管道越长成本越高，所以要求就是管道总长度尽可能短。

一句话概括，就是要用最短的管道覆盖这 6 个房子，问这个路线该怎么设计。这个问题正是普利姆（Prim）算法要解决的问题，也就是寻找最小生成树。

1. 算法过程

整个算法主要是循环两个步骤：

1. 选择一个未被标记过的顶点 A，在其他顶点（B、C、D、E、F）中选出距离 A 最近的顶点 B
2. 遍历 C、D、E、F 顶点，计算 B 到 C 的距离和 A 到 C 的距离，如果 B 到 C 更小，说明走 A 经 B 到 C，比直接连 A 到 B、A 到 C 的权值更低。
3. 重复上面的过程，直到所有的顶点都被计算过。

求这张图的最小生成树时，任意顶点都可以做起始顶点。我们这里选 0 下标的顶点（也就是上图里的 1 号顶点）作为起始顶点，先初始化两个数组：

1. vertex = [0, 0, 0, 0, 0, 0]
2. weight = [0, 7, 9, M, M, 14]

1.1 第 1 次迭代

我们先找距离 1 号顶点最近的顶点，注意到顶点的距离不能为 0：

• 1->1，距离为 0，跳过
• 1->2，距离为 7
• 1->3，距离为 9
• 1->4，距离为 M
• 1->5，距离为 M
• 1->6，距离为 14

最小的距离是 7，对应顶点 2。我们把该顶点在 weight 数组里对应位置的距离改成 0。
接着计算顶点 2 到其他顶点的距离，和起始顶点到其他顶点的距离，如果前者更小，就更新距离：

• 2->1 和 1->1，1 号顶点 weight 为 0，跳过
• 2->2 和 1->2，2 号顶点 weight 为 0，跳过
• 2->3 和 1->3，2->3=10，1->3=9，前者大于后者，什么也不做
• 2->4 和 1->4，2->4=15，1->4=M，前者小于后者，更新 vertex[4] = 2，weight[4] = 15
• 2->5 和 1->5，2->5=M，1->5=M，两者相等，什么也不做
• 2->6 和 1->6，2->6=M，1->6=14，前者大于后者，什么也不做

• vertex = [0, 0, 0, 2, 0, 0]
• weight = [0, 0, 9, 15, M, 14]

1.2 第 2 次迭代

我们从其余 weight 不等于 0 的顶点中，选出 1->x 距离最小的那个：

• 1->1，weight = 0，跳过
• 1->2，weight = 0，跳过
• 1->3，距离为 9
• 1->4，距离为 15
• 1->5，距离为 M
• 1->6，距离为 14

最小距离为 9，对应顶点为 3，我们把该顶点的 weight 设置为 0。
接着计算顶点 3 到其他顶点的距离，和起始顶点到其他顶点的距离：

• 3->1 和 1->1，1 号顶点 weight 为 0，跳过
• 3->2 和 1->2，2 号顶点 weight 为 0，跳过
• 3->3 和 1->3，3 号顶点 weight 为 0，跳过
• 3->4 和 1->4，3->4=11，1->4=M，前者小于后者，更新 vertex[4] = 3，weight[4] = 11
• 3->5 和 1->5，3->5=M，1->5=M，前者等于后者，什么也不做
• 3->6 和 1->6，3->6=2，1->6=14，前者小于后者，更新 vertex[6] = 3，weight[6] = 2

• vertex = [0, 0, 0, 3, 0, 3]
• weight = [0, 0, 0, 11, M, 2]

1.3 第 3 次迭代

我们从其余 weight 不等于 0 的顶点中，选出 1->x 距离最小的那个：

• 1->1，weight = 0，跳过
• 1->2，weight = 0，跳过
• 1->3，weight = 0，跳过
• 1->4，距离为 11
• 1->5，距离为 M
• 1->6，距离为 2

最小距离为 2，对应顶点为 6，我们把该顶点的 weight 设置为 0。
接着计算顶点 6 到其他顶点的距离，和起始顶点到其他顶点的距离：

• 6->1 和 1->1，1 号顶点 weight 为 0，跳过
• 6->2 和 1->2，2 号顶点 weight 为 0，跳过
• 6->3 和 1->3，3 号顶点 weight 为 0，跳过
• 6->4 和 1->4，6->4=M，1->4=11，前者大于后者，什么都不做
• 6->5 和 1->5，6->5=9，1->5=M，前者小于后者，更新 vertex[5] = 6，weight[5] = 9
• 6->6 和 1->6，6 号顶点 weight 为 0，跳过

• vertex = [0, 0, 0, 3, 6, 3]
• weight = [0, 0, 0, 11, 9, 0]

1.4 第 4 次迭代

我们从其余 weight 不等于 0 的顶点中，选出 1->x 距离最小的那个：

• 1->1，weight = 0，跳过
• 1->2，weight = 0，跳过
• 1->3，weight = 0，跳过
• 1->4，距离为 11
• 1->5，距离为 9
• 1->6，weight = 0，跳过

最小距离为 9，对应顶点为 5，我们把该顶点的 weight 设置为 0。
接着计算顶点 5 到其他顶点的距离，和起始顶点到其他顶点的距离：

• 5->1 和 1->1，1 号顶点 weight 为 0，跳过
• 5->2 和 1->2，2 号顶点 weight 为 0，跳过
• 5->3 和 1->3，3 号顶点 weight 为 0，跳过
• 5->4 和 1->4，5->4=6，1->4=11，前者小于后者，更新 vertex[4] = 5，weight[4] = 6
• 5->5 和 1->5，5 号顶点 weight 为 0，跳过
• 5->6 和 1->6，6 号顶点 weight 为 0，跳过

• vertex = [0, 0, 0, 5, 6, 3]
• weight = [0, 0, 0, 6, 0, 0]

1.5 第 5 次迭代

我们从其余 weight 不等于 0 的顶点中，选出 1->x 距离最小的那个：

• 1->1，weight = 0，跳过
• 1->2，weight = 0，跳过
• 1->3，weight = 0，跳过
• 1->4，距离为 6
• 1->5，weight = 0，跳过
• 1->6，weight = 0，跳过

最小距离为 6，对应顶点为 4，我们把该顶点的 weight 设置为 0。
接着计算顶点 4 到其他顶点的距离，和起始顶点到其他顶点的距离：

• 4->1 和 1->1，1 号顶点 weight 为 0，跳过
• 4->2 和 1->2，2 号顶点 weight 为 0，跳过
• 4->3 和 1->3，3 号顶点 weight 为 0，跳过
• 4->4 和 1->4，4 号顶点 weight 为 0，跳过
• 4->5 和 1->5，5 号顶点 weight 为 0，跳过
• 4->6 和 1->6，6 号顶点 weight 为 0，跳过

• vertex = [0, 0, 0, 5, 6, 3]
• weight = [0, 0, 0, 0, 0, 0]

1.6 输出结果

最终结果我们只关心 vertex = [0, 0, 0, 5, 6, 3]，它表示：

1. 第一个顶点连接 0 顶点
2. 第二个顶点连接 0 顶点
3. 第三个顶点连接 0 顶点
4. 第四个顶点连接 5 顶点
5. 第五个顶点连接 6 顶点
6. 第六个顶点连接 3 顶点

这个最小生成树的开销是：7 + 9 + 2 + 9 + 6 = 33。

2. 算法实现

#include <iostream>
#include <list>
using namespace std;

#define M 65535

// 定义顶点
const int vertex_size = 6;
int vertex[] = { 1, 2, 3, 4, 5, 6 };

// 定义边
int edges[][6] = {
	{ 0,  7,  9,  M,  M, 14},
	{ 7,  0,  10, 15, M, M},
	{ 9,  10, 0,  11, M, 2},
	{ M,  15, 11, 0,  6, M},
	{ M,  M,  M,  6,  0, 9},
	{14,  M,  2,  M,  9, 0}
};

void prim()
{	
	// 保存相关顶点的下标
	int vertex[vertex_size];
	// 保存边的权值
	int weight[vertex_size];

	// 最小生成树，可以从任意顶点开始，我们假设从 0 顶点开始
	
	// 记录从初始顶点到其他顶点的距离
	weight[0] = 0;
	vertex[0] = 0;

	// 初始化与初始顶点相关的顶点的边距离
	for (int i = 0; i < vertex_size; ++i)
	{
		vertex[i] = 0;
		weight[i] = edges[0][i];
	}

	for (int i = 0; i < vertex_size; ++i)
	{

		// 搜索与初始顶点距离最近的顶点
		int min = M;
		int k = 0;
		for (int j = 0; j < vertex_size; ++j)
		{	
			// 如果与起始顶点的距离不等于0，并且该顶点与初始顶点的距离小于min
			if (weight[j] != 0 && weight[j] < min)
			{
				min = weight[j];
				k = j;
			}
		}
		
		weight[k] = 0;  // 设置为 0 表示该结点加入最小图中
		// cout << k + 1 << " ";

		// 搜索
		for (int j = 0; j < vertex_size; ++j)
		{
			if (weight[j] != 0 && edges[k][j] < weight[j])
			{
				weight[j] = edges[k][j];
				vertex[j] = k;
			}
		}
	}

	// 打印最小生成树
	for (int i = 0; i < vertex_size; ++i)
	{
		cout << vertex[i] << " ";
	}
	cout << endl;
}


int main()
{
	prim();
	return 0;
}

程序输出结果：

0 0 0 4 5 2

注意一下，程序的输出结果和前面手动算的一致，这里打印出来的是下标。