leetcode 面试题 04.01. 节点间通路 BFS、DFS

题目地址：

https://leetcode.cn/problems/route-between-nodes-lcci/

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例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
提示：

节点数量n在[0, 1e5]范围内。
节点编号大于等于 0 小于 n。
图中可能存在自环和平行边。

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

第一种 转领接表+BFS 方式

    public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 转领接表方便遍历
        List<Integer>[] adj = new ArrayList[n];
        for (int[] edge : graph) {
            int from = edge[0];
            int to = edge[1];
            if (adj[from] == null) {
                adj[from] = new ArrayList<>();
            }
            adj[from].add(to);
        }
        // bfs 遍历
        Queue<Integer> que = new LinkedList<>();
        // 有环需要添加状态标识位,避免死循环
        // n个元素所以长度n就好了，java boolean 默认false
        boolean[] visited = new boolean[n];
        // 添加起点，从起点开始循环
        que.add(start);
        visited[start] = true;
        while (!que.isEmpty()) {
            // 循环当前长度个节点，放到for里面就
            int node = que.poll();
            if (adj[node] == null) {
                // 说明不存在
                continue;
            }
            for (Integer nex : adj[node]) {
                if (nex == target) {
                    // 存在路径说明可达
                    return true;
                }
                if (visited[nex]) {
                	// 访问过就下一个
                    continue;
                }
                // 没访问过，添加进队列
                que.add(nex);
                visited[nex] = 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

第二种 DFS 遍历 + 递归

public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 创建访问状态数组
        boolean[] visited = new boolean[graph.length];
        // DFS
        return dfs(visited, graph, start, target);
    }

    private static boolean dfs(boolean[] visited, int[][] graph, int start, int target) {
        // 深度优先搜索
        for (int i = 0; i < graph.length; ++i) {
            // 确保当前路径未被访问（该判断主要是为了防止图中自环出现死循环的情况）
            if (visited[i]) {
                continue;
            }
            // 若当前路径起点与终点相符，则直接返回结果
            // graph[i][0] 是起点  graph[i][1] 是终点
            if (graph[i][0] == start && graph[i][1] == target) {
                return true;
            }
            // 设置访问标志
            visited[i] = true;
            //DFS关键代码 终点找到后，把当前边起点 作为终点递归
            if (graph[i][1] == target && dfs(visited, graph, start, graph[i][0])) {
                return true;
            }
            // 清除访问标志
            visited[i] = false;
        }
        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
25
26
27
28
29
30
31
32
33
34
35

有兴趣 我们一起每日一题，有疑问也欢迎评论区交流