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

最小生成树：在图论中，常常将树定义为一个无回路连通图（起点和终点相同的路径称为回路）。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。

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

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

1. 算法过程

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

1. 选择一个未被标记过的顶点 A，在其他顶点（B、C、D、E、F）中选择出距离该顶点最近的顶点 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，3->6=2, 1->6=14，顶点 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

注意：我们程序的输出结果和前面手动计算的结果一样，这里输出的是下标。