刷题-Leetcode-面试题 04.01. 节点间通路

刷题-Leetcode-面试题 04.01. 节点间通路 面试题 04.01. 节点间通路 题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/route-between-nodes-lcci/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

参考链接：面试题 04.01. 节点间通路 常规c++使用邻接表，简单通用做法

方法一：BFS（迭代）
1.创建邻接表map
2.定义数组visited(记录访问过的节点)
3.利用queue实现BFS

class Solution {
public:
    bool findWhetherExistsPath(int n, vector>& graph, int start, int target) {
        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;
    }
};

方法二：DFS（递归）
采用递归的方法
1.创建邻接表map和方法一是一样的。
2.由于找到一个结果就立刻返回,利用if(dfs(point,target)) return true;来实现

class Solution {
private:
    vector visited;
    unordered_map> map;
public:
    bool findWhetherExistsPath(int n, vector>& graph, int start, int target) {
        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;
        visited[start] = true;
        for(int point:map[start]){
            if(dfs(point, target)) return true;
        }
        return false;
    }
};