$\Huge\color{orchid}{点击此处获取更多干货}$

Kruskal算法

Kruskal算法是最小生成树的另一种求解方法。之前细心的玩家们大概已经发现了，Prim算法是借助边选取节点，而Kruskal算法是直接选边，按照贪心策略，选出$n-1$条构成最小生成树的边。
下面先给出算法流程：
0. 独立存储每条边$\left \{ s,e,v \right \}$并按照权值$v$升序排列，并将图看成$n$个孤立的，未连接边的节点集合
1. 选取当前权值最小的边，尝试将其连上
2-1. 如果当前边的两个端点$s,e$尚未连通，将其保留下来，权值在总和中累加
2-2. 如果两个端点$s,e$已连通，舍弃当前边，返回步骤1
3. 重复上述步骤直到选完所有边，查看是否选够了$n-1$条边，没有选够就说明求解失败

之前已经说过，无向图连通分量相关问题，是并查集的拿手好活。此外，之前在Bellman-Ford算法部分，已经见过了这种独立存储边的方式，之后的代码中，会借用之前的并查集UnionFind类，以及单独存储边的BFGraph类

C++ 代码

int BFGraph::getSumOfMST() {
    //所有边按照权值val升序排序
    sort(edges.begin(), edges.end(), [](Edge e1, Edge e2) {
        return e1.val < e2.val;
    });
    UnionFind UF(numVex + 1);
    int ans = 0, cnt = 0;
    for(auto& ed : edges) {
        int s = ed.src, e = ed.des, v = ed.val;
        //已经连通了，舍弃它
        if(uf.find(s) == uf.find(e)) {
            continue;
        }
        //未连通，连上这条边，累加
        uf.unite(s, e);
        cnt++;
        ans += v;
    }
    return ((cnt != numVex - 1) ? INT_MIN : ans);
}