Kruskal算法

最小生成树问题一定是针对无向图，Kruskal算法适用于稀疏图

存储结构采用边结构体数组，n为顶点数，m为边数

struct edge {
    int a, b, w;
}graph[m];

Kruskal算法需要借助并查集，流程如下：

(1)将所有边按照边权由小到大排序

bool cmp(edge e1, edge e2) {
    return e1.w < e2.w;
}

sort(graph, graph+m, cmp);

(2)按权值增序遍历所有边，判断边的两个端点是否在一个集合中，如果不在则生成树选中这条边，将两个端点集合合并

for (int i = 0; i < m; i++) {
    auto e = graph[i];
    int x = find(e.a), y = find(e.b);
    if (x != y) {
        set[x] = y;
        // 附加操作
    }
}

注解：

(1)如果需要计算最小生成树边权和，则附加操作将所有选中边的graph[i].w累加

(2)如果需要判断是否有最小生成树，则附加操作累计选中边数，如果最后累计边数为n-1，则有最小生成树

---