最小生成树(Kruskal算法)

---

一下子就接触算法原理和一堆七七八八的术语概念，无疑是让人头疼的，因为无端出现这么多的信息，都不知道它的来历，又不知道这些信息到底有什么用，所以我们就从最简单的内容开始，将这个算法完整地梳理一下吧。

---

1、知识脉络梳理

1、树形结构

首先，先来看看一个简单的数据结构——树。
树形结构，从字面上来理解，就是像我们生活中常见的树长的很类似。在数据结构中我们无非就是将生活中的树倒过来看而已，也就是树根在上，树叶在下。这么设计其实也没什么特别的道理，只是在遍历树的时候，我们从树根开始，从树根往叶子节点出发。但是除了倒着放，其实我们也可以将他伸展开来放，例如下面的这棵树，其实也是一棵树

我们大致的想象一下，就像直接抓着树根将它拎起来，那么就自然变成了上图的样子了。

于是我们就发现，不管拎起是哪个节点，都会得到一棵树。也就是说，如果树根的位置对我们不再重要的话，树其实就等价于上面这样的图。

那么这样的图究竟是什么图呢？它有什么性质呢？所有的图都能看成是树吗？下面我们来看一下三种情况：

显然这三种情况都不是树。第一种是因为图中的边有方向了，一旦有了方向，图中连通的情况就被破坏了。我们都知道，树应该是全部连通的，也就是说你从任意一个节点开始，都可以走到树上任何位置。那么根据定义，不能全连通，肯定就不是树。情况2也不对，因为有了环，树是不应该有环的，大家应该没见过那种从树根还能再到树根的树吧，那不是成了老树精了？在我们定义中的树也是不能有环的，不然我们遍历的时候不是永远也找不到终点了吗？第三种情况则是因为有个别的点孤立在外，因此不能连通，所以也不是树。

所以总结一下，树就是可以全连通的（无向图），并且没有环的图。

2、从图到树

从上面的部分，其实我们可以发现，树的本质就是图，无非就是一些具有特殊性质的图。因此我们也经常能看到许多有关于树的算法会被纳入图论当中。

通过对树的观察，其实我们可以发现一条重要性质，对于一棵拥有n个节点的树而言，它会有n-1条边。因此如果超过n-1条边，证明当中一定存在环路，如果不理解的话，你可以简单画个图尝试一下。反之，如果小于n-1条边，那么一定存在不连通的部分。但我们需要注意，这个性质正向可以成立，反过来就不成立了，用数学中的概念来说就是，它是一个必要条件，但不是一个充分条件。也就是说并不是n个点和n-1条边就一定是树，这个画个图就很容易得出反例。

接下来我们就用这个性质来尝试解决一下由图转化成树的问题。

现在有一个稍微复杂的图，如下图：

那么我们现在就根据这一个图生成一棵能够连通所有节点的树。根据上述的性质，我们的方法很明确，无非就是两种办法：

第一种办法是删边，既然是一个复杂图，说明边的数量肯定要超过n-1的，所以我们可以尝试去删减掉一些边，最后留下一棵树就可以了。

第二种做法则是增边，也就是说我们从零开始，一开始先把所有的边全部撤掉，然后一条一条地往一个集合当中添加n-1条边，让它变成一棵树。

那这两种方法哪种更好呢？我们可以想一下，我们每一次在删除边的时候是不是都需要考虑到是否会破坏树的连通关系，因此添加边的做法明显优于删减边的做法。

可以看看上图，如果我们删除AB这条边，就会发现这个已经不是连通图了，那必然也不可能成为一棵树。要判断连通关系，最好的方法就是先删除这条边，然后试着从A点出发，看看能否到达B点，如果能到达，则认为这条边是可以删除的，但是如果这么做的话，一旦图很大时，每一次删除需要遍历整张图，那么效率就会很低。并且每一次删除后，由于图的结构会发生 变化，我们还需要对这些变化进行存储，但由于他是一直动态变化，存储这些结果十分困难。

因此，删除边的方式可行，但是十分麻烦。

至此，我们知道了其实所谓的最小生成树就是从一个图当中选取n-1条边将他变换为一棵树的算法

3、生成树

我们暂且不考虑带权问题，就先假设所有的边都是等权重的。

那么现在我们知道要采用添加边的方式，那我们选择一条边时，应该怎么判断这条有没有必要添加到集合中去呢？

树有一条性质是，树上任意的两个点，它们之间的路径有且只有一条，如果存在两点之间的路径有两条，那么必然可以形成一个环。那么我们就可以知道如果当前两个点之间已经存在通路的时候，就证明那么当前这两个点连成的边就不能再添加了，否则一定会出现环。因此我们需要设计的算法要维护树上点的连通性。

但是这又会有一个新问题，我们知道，在树结构当中，连通性是可以传递的。如果两个点之间连了一条边，并不仅仅只是这两个点连通，还包括了所有与这两个点之间连通的点都连通了。下面来看一个例子：

这张图当中A和B连了一条边，这不仅仅是A和B连通，而是左半边的集合和右半边集合的连通。所以，虽然A只是和B连通了，但是和C也连通了。AC这条边也一样不能被加入了。也就是说A和B连通，其实是A所在的集合和B所在的集合合并的过程。看到集合的合并我们就可以想到并查集，并查集算法就是用来解决集合合并和查询问题的。那么，显然可以用并查集来维护图中这些点集的连通性。关于并查集，如果不知道的朋友可以点击一下传送门进行了解。

所以，我们现在就得到了生成树。

4、从生成树到最小生成树

现在我们就可以为图中的每条边都加上权重，我们的目标很明确，就是要使得最后生成的树的所有权重之和最小。

比如，看下面这张图，我们现在想要使生成的树上所有边的权重和最小。

根据贪心算法，我们显然希望用尽量短的边来连通树。所以Kruskal算法的原理非常简单，就是对这些边的权值进行排序，依次从短到长遍历这些边，然后通过并查集来查询正在遍历的这条边是否能够被添加，直到所有边都遍历结束。

2、代码实现

1、完美图解

下面图解出自陈小玉老师所主编的书《趣学算法》中，朋友们可以借助理解算法。

2、代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 100;

int nodeset[N];
int n, m;

struct Edge
{	
	int u;
	int v;
	int w;
}e[N * N];

bool comp(Edge x, Edge y)
{
	return x.w < y.w;
}

void Init(int n)
{
	for (int i=1; i < n; i++)
		nodeset[i]=i;
}
int Merge(int a, int b)
{
	int p = nodeset[a];
	int q = nodeset[b];
	if (p == q)
	{
		return 0;
	}
	for (int i = 1; i <= n; i++)//检查所有结点，把集合号是q的改为p
	{
		if (nodeset[i] == q)
			nodeset[i] = p;//a的集合号赋值给b集合号
	}
	return 1;
}
int Kruskal(int n)
{
		int ans = 0;
		for (int i = 0; i < m; i++)
		{
			if (Merge(e[i].u, e[i].v))
			{
				ans += e[i].w;
				n--;
				if (n == 1)
				{
					return ans;
				}
			}
		}
		return 0;
}

int main()
{
	cout << "输入结点数n和边数m:"<<endl;
		cin >> n >> m;
	Init(n);
	cout << "输入结点数u,v和边值w:"<<endl;
		for (int i = 1; i <= m; i++)
			cin >> e[i].u >> e[i].v >> e[i].w;
	sort(e, e + m, comp);
	int ans = Kruskal(n);
	cout << "最小的花费是：" <<ans << endl;
		return 0;
}