最小生成树：Kruskal算法
概览
Kruskal算法（克鲁斯卡尔算法）是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。Kruskal算法是基于贪心的思想得到的。Kruskal算法在图中存在相同权值的边时有效。
问题
给定一个无向图，如果它任意两个顶点都联通并且是一棵树，那么我们就称之为生成树（Spanning Tree）。如果是带权值的无向图，那么权值之和最小的生成树，我们就称之为最小生成树（MST, Minimum Spanning Tree）。 由Kruskal算法，我们可以求得带权无向图的最小生成树的权值之和。
算法描述
算法思想
Kruskal算法是基于贪心的思想得到的。首先把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将两个集合合并，直到所有的点都属于同一个集合为止。合并到一个集合时可以使用并查集优化。换言之，Kruskal算法就是基于并查集的贪心算法。
算法过程
记图中有V个顶点，E条边。 将所有边按权值从小到大排序。排序完成后，我们选择边AD，这样我们的图就变成了下图。 在剩下的边里继续寻找权值最小的，这里找到了CE，它的权值也是5。 依此类推找到DF，AB，BE。 下面继续选择到BC或EF。尽管现在长度为8的边是最小的未选择的边，但现在它们已经连通了（对于BC可以通过CE，EB连接，对于EF可以通过EB，BA，AD，DF连接），所以不需要选择BC或EF。类似地，BD也不需要选择。最后剩下EG和FG，选择权值更小的EG。
算法的简单证明
对图的顶点数n做归纳，证明Kruskal算法对任意n阶图适用： 当n=1时，显然能够找到最小生成树。 假设Kruskal算法对n=k阶图适用，那么，在k+1阶图G中，把权值最小的边的两个端点u和v做合并操作，即把u与v合为一个点v'，把原来接在u和v的边都接到v'上去，这样就能够得到一个k阶图G'，G'的最小生成树T'可以用Kruskal算法得到。 下证T'+{<u,v>}是G的最小生成树。 用反证法，如果T'+{<u,v>}不是最小生成树，设最小生成树是T，即W(T)<W(T'+{<u,v>})。显然T应该包含<u,v>，否则，可以用<u,v>加入到T中，删除环上原有的任意一条边，形成一棵更小权值的生成树，而T-{<u,v>}是G'的生成树（因为G'就是由G中的u，v两点合并产生的），所以W(T')≤W(T-{<u,v>})，即W(T'+{<u,v>})≤W(T)。与W(T)<W(T'+{<u,v>})矛盾。假设不成立。所以T'+{<u,v>}是G的最小生成树，Kruskal算法对k+1阶图也适用。 由数学归纳法，Kruskal算法得证。
程序代码
#include <iostream>
#include <algorithm>
using namespace std;
const int node_num =
100;
struct Edge
{
int u, v, w;
} e[node_num * node_num];
bool cmp(
const Edge &a,
const Edge &b)
{
return a.w < b.w;
}
int main()
{
int v_num;
int a_num;
int sum =
0;
int vset[node_num];
int k =
1;
cout <<
"v_num:";
cin >> v_num;
cout <<
"a_num:";
cin >> a_num;
for (
int i =
0; i < v_num; ++i)
{
vset[i] = i;
}
for (
int i =
0; i < a_num; ++i)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e, e + a_num, cmp);
for (
int index =
0; index < a_num; ++index)
{
int sn1 = vset[e[index].u], sn2 = vset[e[index].v];
if (sn1 != sn2)
{
sum += e[index].w;
++k;
for (
int i =
0; i < v_num; ++i)
{
if (vset[i] == sn2)
{
vset[i] = sn1;
}
}
}
}
if (k == v_num)
{
cout << sum << endl;
}
else
{
cout <<
"E" << endl;
}
return 0;
}
运行结果：
算法优化
并查集与路径压缩概述
并查集（Union Find Sets）是一种用于管理分组的数据结构。它具备两个操作：查询元素a和元素b是否为同一组、将元素a和b合并为同一组。 有一组指针指向每个节点的父节点，根节点的指针指向自己，通过循环就可以找到根节点。 路径压缩，就是在每次查找时，找到根节点，然后令查找路径上的每个节点都直接指向根节点。 将a,b节点合并到同一棵树，就是将a节点的根节点的父节点指针指向b节点的根节点。
实现
int find(
int x) {
int p = x, t;
while (uset[p] != p){
p = uset[p];
}
while (x != p) {
t = uset[x];
uset[x] = p;
x = t;
}
return x;
}
例题
USACO agrinet / POJ 1258
描述
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。
输入输出格式
第一行： 农场的个数，N（3<=N<=100）。 第二行..结尾：接下来的行包含了一个N*N的矩阵，表示每个农场之间的距离。当然，对角线将会是0，因为线路从第i个农场到它本身的距离在本题中没有意义。 只有一个输出，是连接到每个农场的光纤的最小长度和。
样例
SAMPLE INPUT:
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
SAMPLE OUTPUT:
28
程序代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int node_num =
100;
struct Edge
{
int u, v, w;
} e[node_num * node_num];
bool cmp(
const Edge &a,
const Edge &b)
{
return a.w < b.w;
}
int main()
{
int v_num;
while (
cin >> v_num)
{
int vi =
0, sum =
0, vset[node_num], k =
1;
for (
int i =
0; i < v_num; ++i)
{
vset[i] = i;
for (
int j =
0; j < v_num; ++j)
{
e[vi].u = i;
e[vi].v = j;
cin >> e[vi].w;
++vi;
}
}
sort(e, e + vi, cmp);
for (
int index =
0; index < vi; ++index)
{
int sn1 = vset[e[index].u], sn2 = vset[e[index].v];
if (sn1 != sn2)
{
sum += e[index].w;
++k;
for (
int i =
0; i < v_num; ++i)
{
if (vset[i] == sn2)
{
vset[i] = sn1;
}
}
}
}
cout << sum << endl;
}
return 0;
}
POJ 3723
描述
Windy有一个村庄，他想建立一支军队来保护他的村庄。他选了N个女孩和M个男孩，想让他们做自己的士兵。在没有任何关系的情况下，他雇佣一个士兵需要10000元。有一些女孩和男孩之间存在关系，Windy可以利用这些关系省一些花费。如果女孩x和男孩y间存在关系d且他们中的一个人已经被雇佣了，那么Windy可以用10000-d元雇佣他们中的另一个。现在提供女孩和男孩之间的所有关系，你的任务是算出Windy最少要花多少钱。注意，雇佣一个士兵的时候最多只能用一个关系。
输入输出格式
第1行：测试数据组数。 每组测试数据第1行：3个整数N，M，R。 下面R行，每行包含3个整数xi，yi，di。 在每组测试数据后有一个空行。
1≤N,M≤10000 0≤R≤50000
每组输入数据对应一行输出数据。
样例
SAMPLE INPUT:
2
5 5 8 4 3 6831 1 3 4583 0 0 6592 0 1 3063 3 3 4975 1 3 2049 4 2 2104 2 2 781
5 5 10 2 4 9820 3 2 6236 3 1 8864 2 4 8326 2 0 5156 2 0 1463 4 1 2439 0 4 4373 3 4 8889 2 4 3133
SAMPLE OUTPUT:
71071 54223
程序代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int node_num =
20000;
int u[
50000], v[
50000], w[
50000], pre[node_num], p[
50000];
bool cmp(
const int &a,
const int &b)
{
return w[a] > w[b];
}
int findroot(
const int);
int main()
{
int n;
scanf(
"%d", &n);
for (
int N =
0; N < n; ++N)
{
int ngirl, nboy, vi, sum =
0;
scanf(
"%d%d%d", &ngirl, &nboy, &vi);
for (
int i =
0; i < ngirl + nboy; ++i)
{
pre[i] = i;
}
for (
int i =
0; i < vi; ++i)
{
p[i] = i;
}
for (
int i =
0; i < vi; ++i)
{
int t;
scanf(
"%d%d%d", &u[i], &t, &w[i]);
v[i] = t + ngirl;
}
sort(p, p + vi, cmp);
for (
int i =
0; i < vi; ++i)
{
int index = p[i];
int rootx = findroot(u[index]), rooty = findroot(v[index]);
if (rootx != rooty)
{
sum += w[index];
pre[rooty] = rootx;
}
}
sum = (ngirl + nboy) *
10000 - sum;
printf(
"%d\n", sum);
}
return 0;
}
int findroot(
const int x)
{
if (pre[x] == x)
{
return x;
}
return pre[x] = findroot(pre[x]);
}
参考
最小生成树之Kruskal算法最小生成树-Prim算法和Kruskal算法【模版】并查集 及路径压缩
