Kruskal算法是求最小生成树的一种算法，运用了贪心的思想，十分常用。算法流程大体如下：将m条边按边权从小到大排序，枚举每条边，如果该边的起点和终点已经在最小生成树中，则跳过，否则就将这条边加入到最小生成树中。具体实现方面会借助于并查集，来判断两个点是否在最小生成树中（已连通）。
1 #include2 #include 3 4 using namespace std; 5 6 struct Edge { 7 int u, v, w; 8 bool operator < (const Edge& rhs) const { 9 return w < rhs.w;10 } //规定边的优先级用于排序11 } edge[maxm];12 13 int n, m, fa[maxn];14 15 int dj_find(int i) {16 if (i == fa[i]) return i;17 else return fa[i] = dj_find(fa[i]);18 }19 20 inline void dj_merge(int a, int b) {21 a = dj_find(a), b = dj_find(b);22 if (a != b) fa[a] = b;23 } //定义并查集的查询合并操作24 25 inline int Kruskal() {26 int cnt = 0, sum = 0;27 for (int i = 1; i <= n; ++i) fa[i] = i;28 sort(edge + 1, edge + m + 1); //按边权排序29 for (int i = 1; i <= m; ++i) {30 int u = edge[i].u, v = edge[i].v;31 if (dj_find(u) != dj_find(v)) {32 dj_merge(u, v);33 sum += edge[i].w;34 ++cnt;35 } //若边的起点和终点之前未连通，则连通36 if (cnt == n - 1) return sum;37 } //最小生成树有n-1条边38 return -1;39 }
呃呃，附上一道裸题，USACO习题最短网络，在洛谷上的链接为：