C++算法集锦：图论

class="superseo">图论

• 最小生成树

最小生成树

牛客连接： 最小生成树

解法1
思路：kruskal算法+并查集

利用kruskal的思想，每次选择最短的路径，加入到候选集和中，从而最终连通整个图。
这里同时采用并查集的思想，每次将一条对一条候选路径进行选择的时候，判断两个端点是否拥有共同父亲，如果拥有则表明这两个点之间已经存在被加入候选集合中了，放弃这条边；如果没有拥有共同父亲，则将两个点连接，即指定一个点为另一个点的父亲，并且选择这条边加入连通图。最终，判断完所有的路径。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    static bool comp(const vector<int >& x, const vector<int >& y){
        return x[2] < y[2];
    }
    int find_father(int &x, vector<int> &parents){
        return (parents[x] == x)?x:find_father(parents[x],parents);
    }    
    
    
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        sort(cost.begin(),cost.end(),comp);
        int sum = 0;
        vector<int> parents(n+1);
        for(int i =0;i<=n;++i)         //建立并查集
            parents[i] = i;
        for(vector<int> i : cost){    //优先查找最路径
            int x = i[0];
            int y = i[1];
            int exp = i[2];
            x = find_father(x,parents);  //合并
            y = find_father(y,parents);
            if(x!=y){
                parents[x] = y;
                sum+=exp;
            }
        }
        return sum;
    }
};

解法2
思路：prim算法

#include 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    static bool comp(const vector<int> &x, const vector<int> &y){
        return x[2]<y[2];
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        unordered_set<int> points;      //纳入确定集合
        sort(cost.begin(),cost.end(),comp);   //路径排序 保证优先查找到每个端点最短路径
        points.insert(cost[0][0]);			//最短路径两个端点先纳入集合
        points.insert(cost[0][1]);
        int res = cost[0][2];			
        cost.erase(cost.begin());
        while(true){                    //递归向外拓展最短路径
            if(points.size()==n)
                break;
            for(int i =0; i<cost.size(); ++i){   
            	//一个端点在集合内一个端点不在集合内
                if((points.find(cost[i][0])!=points.end() && points.find(cost[i][1])==points.end()) || 
                   (points.find(cost[i][0])==points.end() && points.find(cost[i][1])!=points.end())){
                    res+=cost[i][2];
                    points.insert(cost[i][0]);
                    points.insert(cost[i][1]);
                    cost.erase(cost.begin()+i);
                    break;
                }

            }
        }
        return res;
    }
};