Kruskal算法是解决最小生成树问题的一种算法。其算法过程是
- 一开始，所有点都是孤立的点。
- 对所有的边从小到大排序
- 每次选取权值最小且其两个顶点还不连通的边
- 连通选取的边的两个顶点
- 重复这个过程，直到所有的顶点连通
问题：什么时候停止循环?
答案：选取了n-1条边
问题：为什么是n-1条边？选取了n-1条边就保证n个顶点连通了?
答案：n个顶点连通，且不构成回路，需要n-1条边。那存在n-1条边，并且不构成回路，那么通过这n-1条边，n个顶点就是连通的。
在Kruskal算法中，每次选取一条权值最小边且其两个顶点还不连通，每次选一条边，有三种情况：一是两个顶点自成一派，都是孤立的点，二是一个顶点在已知连通分量里，另一个顶点是孤立的点，三是两个顶点在两个未连通的已知连通分量里，第一种情况的两个顶点连通后，成为单独的连通分量，这种情况增加一条边，增加两个顶点。第二种情况的两个顶点连通后，已知连通分量增加一个顶点，这种情况增加一条边，增加一个顶点。第三种情况的两个顶点连通后，两个未连通的已知连通分量连通了，这种情况增加一条边，顶点的个数不变。问题是选取n-1条这样的边，为什么n个顶点就都连通了?。如果n个顶点中存在n-1条不构成回路的边，那么这n个顶点就是连通的。可以简单的用数学归纳法证明。
当n=2时，如果存在1条边，显然这两个顶点是连通的。
假设n = m,并且存在m-1条不构成回路的边，m个顶点是连通的。当n=m+1时，即在顶点数为m的情况下，增加一个点和一条边，因为要不构成回路，增加的边不能加在原来的m个顶点里，只能加在新增的点上，用来连接新增的点和原来m个点中的任何一个，所以当n=m+1，并且存在m条不构成回路的边的情况下，m+1个顶点也是连通的。
因为每次选择的都是权值最小的边，所以最后的结果就是最小生成树。这是贪心策略的体现。
还要说明的一点是查询两个点是否已经在同一连通分量上，用的是并查集。
代码如下：
//表示边
struct Edge {
int u;//起点
int v;//终点
int w;//权重
};
///假设有编号从1到n的n个顶点,m条边
class Kruskal {
vector<int> boss;
public:
static bool compreEdge(Edge &e1, Edge &e2) {
return e1.w < e2.w;
}
vector<Edge> minimumSpanningTree(vector<Edge> &edges,int n) {
for(int i = 0;i <= n;i++) {
boss.emplace_back(i);
}
sort(edges.begin(), edges.end(), compreEdge);
vector<Edge> ans;
int count = 0;
for(int i = 0;i < edges.size();i++) {
Edge edge = edges[i];
if (merge(edge.u, edge.v)) {
ans.emplace_back(edge);
count++;
}
if (count == n - 1) {
break;
}
}
return ans;
}
int getBoss(int u) {
if (boss[u] == u) {
return u;
}
else {
boss[u] = getBoss(boss[u]);
return boss[u];
}
}
bool merge(int u, int v) {
int t1 = getBoss(u);
int t2 = getBoss(v);
if (t1 == t2) {
return false;
}
boss[t2] = t1;
return true;
}
};