对于一个给定的连通的无向图 G = (V, E)，希望找到一个无回路的子集 T，T 是 E 的子集，它连接了所有的顶点，且其权值之和为最小。
因为 T 无回路且连接所有的顶点，所以它必然是一棵树，称为生成树（Spanning Tree），因为它生成了图 G。显然，由于树 T 连接了所有的顶点，所以树 T 有 V – 1 条边。一张图 G 可以有很多棵生成树，而把确定权值最小的树 T 的问题称为最小生成树问题（Minimum Spanning Tree）。术语 “最小生成树” 实际上是 “最小权值生成树” 的缩写。
Kruskal 算法提供一种在 O(ElogV) 运行时间确定最小生成树的方案。Kruskal 算法基于的思想进行设计，其选择的贪心策略就是，每次都选择权重最小的但未形成环路的边加入到生成树中。其算法结构如下：
- 将所有的边按照权重非递减排序；
- 选择最小权重的边，判断是否其在当前的生成树中形成了一个环路。如果环路没有形成，则将该边加入树中，否则放弃。
- 重复步骤 2，直到有 V – 1 条边在生成树中。
上述步骤 2 中使用了 来判断是否存在环路。
例如，下面是一个无向连通图 G。
图 G 中包含 9 个顶点和 14 条边，所以期待的最小生成树应包含 (9 – 1) = 8 条边。
首先对所有的边按照权重的非递减顺序排序：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Weight Src Dest 1 7 6 2 8 2 2 6 5 4 0 1 4 2 5 6 8 6 7 2 3 7 7 8 8 0 7 8 1 2 9 3 4 10 5 4 11 1 7 14 3 5 |
然后从排序后的列表中选择权重最小的边。
1. 选择边 {7, 6}，无环路形成，包含在生成树中。
2. 选择边 {8, 2}，无环路形成，包含在生成树中。
3. 选择边 {6, 5}，无环路形成，包含在生成树中。
4. 选择边 {0, 1}，无环路形成，包含在生成树中。
5. 选择边 {2, 5}，无环路形成，包含在生成树中。
6. 选择边 {8, 6}，有环路形成，放弃。
7. 选择边 {2, 3}，无环路形成，包含在生成树中。
8. 选择边 {7, 8}，有环路形成，放弃。
9. 选择边 {0, 7}，无环路形成，包含在生成树中。
10. 选择边 {1, 2}，有环路形成，放弃。
11. 选择边 {3, 4}，无环路形成，包含在生成树中。
12. 由于当前生成树中已经包含 V – 1 条边，算法结束。
#include#include #include #include #define MAX 1000using namespace std;int father[MAX];int son[MAX];int v, l;//瀛樺偍杈逛俊鎭struct Edge { int begin; int end; int weight;};bool cmp(const Edge &a, const Edge &b) { return a.weight < b.weight;}int unionsearch(int x) { return x == father[x] ? x : unionsearch(father[x]);}bool join(int x, int y) { int root1, root2; root1 = unionsearch(x); root2 = unionsearch(y); if(root1 == root2) { return false; } else if(son[root1] >= son[root2]) { father[root2] = root1; son[root1] += son[root2]; } else { father[root1] = root2; son[root2] += son[root1]; } return true;}int main(){ int ncase = 0, ltotal = 0, sum = 0, flag = 0; Edge edge[MAX]; scanf("%d", &ncase); while(ncase--) { scanf("%d%d", &v, &l); ltotal = 0; sum = 0; flag = 0; for(int i = 0; i < v; i++) { father[i] = i; son[i] = 1; } for(int i = 0; i < l; i++) { scanf("%d%d%d", &edge[i].begin, &edge[i].end, &edge[i].weight); } //鏉冨€肩敱灏忓埌澶ф帓鍒 sort(edge, edge + l, cmp); for(int i = 0; i < l; i++) { if(join(edge[i].begin, edge[i].end)) { ltotal++; sum += edge[i].weight; cout << edge[i].begin << "->" << edge[i].end <