图的搜索

bfs

dfs

进阶

最小生成树

Kruskal算法

思想：每次知道候选边中权值最小的边，并入生成树中（不能构成环—并查集）

**执行过程：**将图中边按照权值从小到大排序，然后从最小边开始扫描，并检测当前边是否为候选边，即是否该边的并入会构成回路。

并查集---使用数组存储（树的双亲存储结构）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    static bool cmp(vector<int>& x, vector<int>& y)
    {
        return x[2] < y[2];
    }//重载比较，按照边权递增
    
    int find(vector<int>& parent, int x){
        if(parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }//找到最高的父亲
    
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        vector<int> parent(n+1);
        for(int i = 0; i <= n; i++){
            parent[i] = i;
        }//初始化，父亲设定为自己，每一颗树的根节点都是自己
        sort(cost.begin(), cost.end(), cmp); //边权递增排序
        int res = 0;
        for(int i = 0; i< cost.size(); i++)
        {
            int x = cost[i][0];
            int y = cost[i][1];
            int z = cost[i][2];
            int px = find(parent, x); //去找到x的根节点
            int py = find(parent, y); //去找到y的根节点
            if(px != py){
                res += z;//，不构成环，边加入
                parent[px] = py; //并入树中
            }  
        }
        return res;//返回耗损
        
    }
};