Kruskal算法通过排序边和并查集检测环，逐步选择最小权重边构建最小生成树。首先定义边结构体并按权重排序，使用并查集判断顶点连通性，避免成环。初始化每个顶点的父节点为自身，遍历排序后的边，若两端点不在同一集合，则加入生成树并合并集合。最终得到包含所有顶点的无环连通子图。该方法时间复杂度为O(E log E)，适用于稀疏图。示例中5个顶点6条边，经排序与并查集处理后输出最小生成树各边及其权重。核心在于贪心策略与高效连通性检查的结合。
Kruskal算法用于求解无向图的最小生成树（MST），核心思想是按边的权重从小到大排序，依次选择边并避免形成环，直到生成树包含所有顶点。在C++中，通常结合并查集（Union-Find）来高效判断是否成环。
1. 数据结构设计
需要定义边的结构体，并实现并查集来管理顶点的连通性。
struct Edge {
int u, v, weight;
立即学习“C++免费学习笔记（深入）”；
Edge(int u, int v, int w) : u(u), v(v), weight(w) {}
};
使用vector存储所有边，并按权重排序：
bool cmp(Edge a, Edge b) {
return a.weight
}
2. 并查集实现
并查集用于快速查找根节点和合并集合，防止加入边后形成环。
int find(vector
if (parent[x] != x)
parent[x] = find(parent, parent[x]); // 路径压缩
return parent[x];
}
void unite(vector
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX]
parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
3. Kruskal主函数
将所有边排序后逐个尝试加入生成树，使用并查集检查连接性。
vector
vector
C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。
sort(edges.begin(), edges.end(), cmp);
vector
vector
// 初始化并查集
for (int i = 0; i
parent[i] = i;
for (Edge& e : edges) {
int u = e.u, v = e.v;
if (find(parent, u) != find(parent, v)) { // 不连通
result.push_back(e);
unite(parent, rank, u, v); // 合并集合
}
}
return result;
}
4. 使用示例
假设有5个顶点和6条边：
int main() {
int n = 5;
vector
edges.push_back(Edge(0, 1, 2));
edges.push_back(Edge(0, 3, 6));
edges.push_back(Edge(1, 2, 3));
edges.push_back(Edge(1, 3, 8));
edges.push_back(Edge(1, 4, 5));
edges.push_back(Edge(2, 4, 7));
vector
cout
for (Edge& e : mst) {
cout
}
return 0;
}
基本上就这些。关键在于边排序和并查集的配合使用，确保每次选的都是当前最短且不会成环的边。时间复杂度主要由排序决定，为 O(E log E)，适合稀疏图。
