数据结构——最小连通图

无向图的最小连通分量——Kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

参考文章图解：什么是最小生成树？

    vector<int> parents;
    int count;
    void init(int n){
        count = n+1;
        parents = vector<int>(n+1, 0);
        for(int i=0; i<=n; ++i){
            parents[i] = i;
        }
    }

    int find(int x){
        if(x != parents[x])
            return find(parents[x]);
        return parents[x];
    }

    void Union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY)
            return ;
        parents[rootX] = rootY;
        count--;
        }

    bool isConnected(int x, int y){
        return find(x) == find(y);
    }
	/*
	输入：
		n， 节点数量
		connections， {{a, b, w}} 无向图中的起点、终点、权重
	*/
    int minimumCost(int n, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(), [&](vector<int>& a, vector<int>& b){
            return a[2] < b[2];
        });
        init(n);
        int ans = 0;
        for(int i=0; i<connections.size(); ++i){
            int x,y,w;
            x = connections[i][0];
            y = connections[i][1];
            w = connections[i][2];

            if(! isConnected(x, y)){
                Union(x, y);
                ans += w;
            }

        }
        return count == 2? ans : -1;
    }

无向图的最小连通分量——Prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

class Solution {
public:
    using rhs = pair<int, int>;

    int minimumCost(int n, vector<vector<int>>& connections) {
        vector<vector<rhs>> edge(n+1);
        for(auto x : connections){
            int a = x[0];
            int b = x[1];
            int w = x[2];
            edge[a].push_back(make_pair(w, b));
            edge[b].push_back(make_pair(w, a));
        }
        priority_queue<rhs, vector<rhs>, greater<rhs>> m_que;
        m_que.push(make_pair(0, 1));
        vector<bool> used(n+1, false);

        int res = 0;
        int cnt = 0;

        while(m_que.size()){
            auto top = m_que.top();
            m_que.pop();
            int cost = top.first;
            int b = top.second;
            if(used[b]){
                continue;
            }
            used[b] = true;
            res += cost;
            cnt++;
            for(auto x : edge[b]){
                int y = x.second;
                int w = x.first;
                if(!used[y]){
                    m_que.push(make_pair(w, y));
                }
            }
        }
        if(cnt == n)
            return res;
        return -1;

    }
};