克鲁斯卡尔算法和普利姆算法一样，都是用来构建最小生成树的。普利姆的思路是盯着每个顶点去找权值最小的边，克鲁斯卡尔则反过来，直接从边的角度去找权值最小的边。

1. 算法过程

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

// 邻接矩阵
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.1 第 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 步迭代

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

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

接下来设置 parent_vertex[4] = 5，表示这条边已经收录，且 4 有了父顶点。此时如下图：

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

1.3 第 3 步迭代

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

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

接下来设置 parent_vertex[1] = 2，表示这条边已经收录，且 1 有了父顶点。此时如下图：

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

后面就照这个节奏一步步走下去，直到所有边都遍历完，就得到一棵最小生成树。如下图：

2. 算法实现

实现代码里用了 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;
}

程序输出结果：

克鲁斯卡尔算法（Kruskal）