算法分享之图的dfs和bfs

dfs即深度优先搜索，在遍历的图的时候每次从一个点到不重复访问的它能前往的最深处的点，然后再访问该点的另一条边。

而bfs即广度优先搜索，在遍历图的时候每次将与这个点连接的所有点都访问了，再进入子节点的子节点。

dfs常采用递归，递归进入与之连接的结点，然后到叶结点时，能够回到父问题即父结点，然后继续遍历其他的边。而bfs常借助队列，将与根结点连接的结点依次加入队列，然后依次访问队列，加入队列，每次则会优先访问与该结点连接的所有结点。

图的dfs和bfs的题在牛客网可以参考最多结点数 ，树的bfs和dfs的题在牛客网上可以参考二叉树的深度 。

下面以图的dfs和bfs应用为例子，本题的具体题解可以参考这篇题解

方法一：dfs

首先我们构建图。然后从节点1开始进行深度优先搜索，遍历与其相连的每一个节点，每到一个节点不能遍历前序节点或者已经访问过的，然后每次需要判断是否回到了节点1，如果没有则继续深度优先搜索往下走，如果最后也没有回到节点1，返回false。

class Solution {
public:
    bool dfs(int cur, int pre, vector<vector<int>>& G, vector<int>& vis){
        for(int i = 0; i < G[cur].size(); i++){ //遍历每个节点
            int next = G[cur][i];
            if(next == pre) //不能是前序节点
                continue;
            if(!vis[next]){
                vis[next] = true;
                if(next == 1 || dfs(next, cur, G, vis)) //回到了1或者子节点的dfs回到了1
                    return true;
            }
        }
        return false;
    }
    string solve(vector<int>& param, vector<Point>& edge) {
        int n = param[0];
        int m = param[1]; //先找到m和n
        vector<vector<int> > G(n + 1);
        vector<int> vis(n + 1, 0);  //记录是否访问过
        for(int i = 0; i < m; i++){ //构建图
            G[edge[i].x].push_back(edge[i].y);
            G[edge[i].y].push_back(edge[i].x);
        }
        if(dfs(1, -1, G, vis)) //深度优先搜索判断
            return "Yes";
        return "No";
    }
};

方法二：bfs

同理，有dfs就会有bfs。我们可以广度优先搜索与节点1相连的所有结点，并对其每个做一个单独的标记，然后继续广度优先搜索，子节点的的标记就等于父节点的标记（只有节点1相连的不一样），如果广度优先搜索到后面，遇到相邻两个不相同标记的节点，说明这里可以构成一圈即一个回路。
如下图所示：

class Solution {
public:
    string solve(vector<int>& param, vector<Point>& edge) {
        int n = param[0];
        int m = param[1]; //先找到m和n
        vector<vector<int> > G(n + 1);
        vector<int> vis(n + 1, -1);  //记录是否访问过
        for(int i = 0; i < m; i++){ //构建图
            G[edge[i].x].push_back(edge[i].y);
            G[edge[i].y].push_back(edge[i].x);
        }
        queue<int> q; //bfs辅助队列
        q.push(1);
        vis[1] = 0; //从1号开始访问
        while(!q.empty()){ //bfs
            int cur = q.front();
            q.pop();
            for(int i = 0; i < G[cur].size(); i++){
                int next = G[cur][i];
                if(vis[next] == -1){ //未访问过
                    q.push(next); //进入队列后续访问
                    if(cur == 1)  //标记
                        vis[next] = i + 1;
                    else
                        vis[next] = vis[cur];
                }else{
                    if(vis[next] != vis[cur] && next != 1) //不同点相遇，有回路
                        return "Yes";
                }
            }
        }
        return "No";
    }
};