克鲁斯卡尔算法（Kruskal）-工具盒子

克鲁斯卡尔算法和普利姆算法一样，用于构建最小生成树。普利姆算法基本思想就是寻找每个顶点权值最小的边，而克鲁斯卡尔算法则是依据边来寻找权值最小的边。

算法过程 {#title-0} ==================

上图的邻接矩阵表示如下：

// 邻接矩阵
int edges[][vertex_size] = {
	{ 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}
};

由于克鲁斯卡尔算法是基于边来构建最小生成树，所以第一步就要将我们构建的邻接矩阵，转换为边数组 edge_set，并对边数组根据 weight 升序排列：

begin     end       weight
3         6         2
4         5         6
1         2         7
1         3         9
5         6         9
2         3         10
3         4         11
1         6         14
2         4         15

另外初始化 parent_vertex 顶点数组全部为 0，该数组用于检查新的边是否和已经构建好的边产生环路。

{0, 0, 0, 0, 0, 0}

**注意：**边数组一定要根据 weight 升序排列，这会使得我们优先遍历低权重的边，优先将其添加到边结果中。

第 1 步迭代 {#title-1}

从 edge_set 取出第 1 个边：(begin, end, weight) = (3, 6, 2)，借助 parent_vertex 数组，查看 begin 和 end 的最顶层顶点是否是相等的，如果两个顶点相等说明，新的边添加进来的话，会使得构建的最小生成树出现环路的问题。

顶点 3 和顶点 6 的位置为 0，表示其没有父顶点。即：该边的加入不会导致环路。所以，我们设置 parent_vertex[3] = 6，并且打印 3->6 这条边，如下图所示：

// 假设索引从 1 开始
parent_vertex = {0, 0, 6, 0, 0, 0}

1.2 第 2 步迭代 {#title-2}

重复前面的过程，从 edge_set 取出第 2 个边 (begin, end, weight) = (4, 5, 6)：

顶点 4 的父顶点为 0，表示没有父顶点；
顶点 5 的父顶点为 0，表示没有父顶点；
4 不等于 5，表示该边的加入不会导致环路。

接下来设置 parent_vertex[4] = 5，表示该边已经存在，并且该边是有父顶点。此时如下图所示：

// 假设索引从 1 开始
parent_vertex = {0, 0, 6, 5, 0, 0}

1.3 第 3 步迭代 {#title-3}

从 edge_set 取出第 3 个边 (begin, end, weight) = (1, 2, 7)，计算每个顶点的祖宗顶点：

顶点 1 的父顶点为 0，表示没有父顶点；
顶点 2 的父顶点为 0，表示没有父顶点；
1 不等于 2，表示该边的加入不会导致环路。

{#block-0f64af4f-4e8b-434f-b37a-aa646079143f}

接下来设置 parent_vertex[1] = 2，表示该边已经存在，并且该边是有父顶点。此时如下图所示：

// 假设索引从 1 开始
parent_vertex = {2, 0, 6, 5, 0, 0}

...依次类推，直到所有的边都遍历完毕，我就会得到一个最小生成树。如下图所示：

算法实现 {#title-4} ==================

代码在实现过程中使用 STL 的 multiset 容器，该容器基于红黑树，内部能够自行排序，节省了自己的排序操作。

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

#define M 65535

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

// 定义边
int edges[][vertex_size] = {
	{ 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}
};


struct Edge
{
	Edge() {}
	Edge(int b, int e, int w) : begin(b), end(e), weight(w) {}

	bool operator<(const Edge &edge) const
	{
		return weight < edge.weight;
	}

	int begin;
	int end;
	int weight;
};


int get_origin_vertex(int vertex[], int current_vertex)
{
	// 假设当前顶点为起始顶点
	int origin_vertex = current_vertex;
	// 不断向上追溯其真正的起始顶点
	// 如果 vertext[origin_vertex] = 0 说明不再有父顶点
	while (vertex[origin_vertex] > 0)
	{
		origin_vertex = vertex[origin_vertex];
	}

	return origin_vertex;
}

void kruskal()
{	
	// 初始化边集，并将其根据 weight 升序排列
	multiset<Edge> edge_set;
	for (int i = 0; i < vertex_size; ++i)
	{
		for (int j = i + 1; j < vertex_size; ++j)
		{
			if (edges[i][j] != M)
			{	
				edge_set.insert(Edge(i, j, edges[i][j]));
			}
		}
	}

	// parent_vertex 用于记录顶点的父顶点，便于检查新的边是否会和已经构建好的边构成环路
	int parent_vertex[vertex_size] = { 0 };
	
	// 遍历所有的边
	for (auto &v : edge_set)
	{	

		// 获得当前边的开始顶点的祖宗顶点
		int origin_begin = get_origin_vertex(parent_vertex, v.begin);
		// 获得当前边的结束顶点的祖宗顶点
		int origin_end = get_origin_vertex(parent_vertex, v.end);

		if (origin_begin != origin_end)
		{
			// 进入此条件，说明新的边不会形成环路
			parent_vertex[origin_begin] = origin_end;
			// 打印新的边
			cout << v.begin << " " << v.end << endl;
		}
	}
}

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

程序输出结果：