Cinte's Leetcode Record
0%

面试题 04.01. 节点间通路

Posted on Edited on In Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

面试题 04.01. 节点间通路

##### BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        unordered_map<int, vector<int>> map;
        for(auto& node : graph)
            map[node[0]].push_back(node[1]);
        queue<int> q;
        q.push(start);
        while(!q.empty())
        {
            for(int i = 0, j = q.size(); i < j; ++i)
            {
                auto p = q.front();
                if(p == target)
                    return true;
                q.pop();
                for(auto next : map[p])
                    q.push(next);
            }
        }
        return false;
    }
};
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        visited = vector<int>(n, 0);
        for(auto& node : graph)
            map[node[0]].push_back(node[1]);
        return dfs(start, target);
    }
private:
    unordered_map<int, vector<int>> map;
    vector<int> visited;
    bool dfs(int cur, int target)
    {
        if(cur == target)
            return true;
        for(auto next : map[cur])
            if(dfs(next, target))
                return true;
        return false;
    }
};

防止重复访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        visited = vector<int>(n, 0);
        for(auto& node : graph)
            map[node[0]].push_back(node[1]);
        return dfs(start, target);
    }
private:
    unordered_map<int, vector<int>> map;
    vector<int> visited;
    bool dfs(int cur, int target)
    {
        if(visited[cur])
            return false;
        visited[cur] = 1;
        if(cur == target)
            return true;
        for(auto next : map[cur])
            if(dfs(next, target))
                return true;
        return false;
    }
};
不用hash，直接用如图的graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        visited = vector<int>(graph.size(), 0);
        return dfs(start, target, graph);
    }
private:
    vector<int> visited;
    bool dfs(int start, int target, vector<vector<int>>& graph)
    {
        for(int i = 0; i < graph.size(); ++i)
        {
            if(!visited[i])
            {
                if(graph[i][0] == start && graph[i][1] == target)
                    return true;
                visited[i] = 1;
                // 如果[1]等于target那么[0]也可以到，所以成为新的target
                if(graph[i][1] == target && dfs(start, graph[i][0], graph))
                    return true;
                visited[i] = 0; 
            }
        }
        return false;
    }
};

回溯，防止重复访问，然后缩短结尾区间。 // 缩短开头理论上也行