面试题 04.01：节点间通路

• 题目
• 解题
• • 方法一：BFS(迭代)
  • 方法二：DFS(迭代)
  • 方法三：DFS(递归）

题目链接
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:

 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 输出：true

示例2:

 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 输出 true

1.建立邻接表,利用visited数组记录节点是否访问过
2.利用queue进行BFS
3.遍历当前节点的邻接节点，然后返回步骤2,

class Solution {
public:
    bool findWhetherExistsPath(int n, vector>& graph, int start, int target) {
        if(start==target) return true;
        unordered_map> map;
        for(vector& vec:graph){
            map[vec[0]].push_back(vec[1]);
        }
        vector visited(n,false);
        queue queue;
        queue.push(start);
        while(!queue.empty()){
            int cur=queue.front();
            queue.pop();
            visited[cur]=true;
            for(int point:map[cur]){
                if(point==target) return true;
                else if(visited[point]==false) queue.push(point);
            }
        }
        return false;
    }
};

和广度优先搜索写法上基本无差别，只不过深度优先使用了stack，而广度优先使用了queue。

class Solution {
public:
    bool findWhetherExistsPath(int n, vector>& graph, int start, int target) {
        if(start==target) return true;
        unordered_map> map;
        for(vector& vec:graph){
            map[vec[0]].push_back(vec[1]);
        }
        stack st;
        st.push(start);
        vector visited(n,false);
        while(!st.empty()){
            int cur=st.top();
            st.pop();
            visited[cur]=true;
            for(int point:map[cur]){
                if(point==target) return true;
                else if(visited[point]==false){
                    st.push(point);
                }
            }
        }
        return false;
    }
};

构造邻接表还是一样的。
由于出现一个满足条件的路径就返回，于是dfs的返回值是bool
if(dfs(point,target)) return true; 一旦出现一个true，就递归返回，最终返回结果true;

中止条件：
1.start==end
2.visited[start]==true

class Solution {
private:
    vector visited;
    unordered_map> map;
public:
    bool findWhetherExistsPath(int n, vector>& graph, int start, int target) {
        if(start==target) return true;
        for(vector& vec:graph){
            map[vec[0]].push_back(vec[1]);
        }
        visited=vector(n,false);
        return dfs(start,target);
    }
    bool dfs(int start,int target){
        if(start==target) return true;
        if(visited[start]) return false;
        visited[start]=true;
        for(int point:map[start]){
            if(dfs(point,target)) return true;
        }
        return false;
    }
};