开头

居然没有咕咕咕
看来本小姐还是很勤奋的嘛!

正文

上。。上次不是写了个 普里姆 (Prim) 的最小生成树算法嘛。。。
然。。然后一不小心就开了个坑
不过, 本小姐现在可是已经填了这个坑了哦!

那么, 在这一篇辣鸡博客里本小姐将会介绍 最小生成树 的第二种算法 克鲁斯卡尔 (Kruskal)
~~这名字怎么这么难记。。~~

同样, 先上图(数据来自《大话数据结构》) ~~(因为没有保存图的数据。。所以这一次的图可能会跟上次的图的顶点有点偏差, 不过数据是一模一样的!)~~

上一个算法(普里姆 Prim) 是从顶点出发, 构建最小生成树的
而这一次要介绍的 克鲁斯卡尔 (Kruskal) ~~这也太难记了~~ 则是从边出发的
首先, 将所有的边排好序, 从最短边出发(3-6 (7))
判断这条边加入最小生成树后, 是否会成环
显然, 最小生成树里什么都没有, 那么就将 3-6 (7) 放进最小生成树里

接下来到了第二小的边 1-7 (8)
判断是否会成环, 然后根据结果选择是否添加…

如此循环下去, 直到…

到这里的时候, 第 n 小的边是 4-5 (17)
但是检验是否成环的时候发现
如果这条边加入了最小生成树, 那么将会有 环 出现
因此忽略掉 (心疼 4-5 (17))

同样, 8-1 (18) 也是会成环, 忽略

直到把所有边都遍历完毕后, 最终的生成树, 会是这个样子的

怎么样, 在本小姐的悉心指导下, 是不是学的很轻松
~~明明是 Kruskal 本来就很简单~~

克鲁斯卡尔 (Kruskal) 算法 ~~真的想给它重新名一个名字。。~~
思路上很简单, 也十分暴力
就是将所有边从小到大排序好
并遍历它们, 如果这条边加入后不会成环, 那么就放心的加入到最小生成树
如果加入后会成环, 就忽略它

示例代码(选自《大话数据结构》, 有少量删改):

// 通过一个顶点来找到包含这个顶点的 最小生成树 的父节点
auto find(const size_t *parent, size_t f) -> size_t {
	while (parent[f] > 0) f = parent[f];
	return f;
}

auto miniSpanTree(const std::vector<Edge> &edges) -> void {
	size_t parent[MAX];     // 用来判断是否成环, 在另一种角度上可以把这个看成是 最小生成树 
	std::memset(parent, 0, sizeof(size_t) * MAX);   // 初始化

	for (const auto &edge : edges) {    // 遍历所有边
		size_t n = find(parent, edge.begin);    // 找到包含 edge.begin 的父节点
		size_t m = find(parent, edge.end);      // 找到包含 edge.end 的父节点

		if (n != m) {       // 如果这两个父节点不相同, 那么可以通过这一条边将他们连起来
			std::cout << edge.to_string() << std::endl;     // 输出边
			parent[n] = m;      // 更新最小生成树 
		}

        // 如果父节点相同, 加入这条边后就会成环, 因此选择忽略
	}
}

事实上, 本小姐对判断是否成环的代码并不是很懂。。。
这。。这是秘密哦, 不要跟其他人说。。

原来是并查集呀, 本小姐差不多理解并查集了
本小姐真是个甜菜, 哈哈哈哈