LeetCode 面试题 04.01. 节点间通路

约 4 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 程序员面试金典（第 6 版） 虾皮
标签
深度优先搜索 广度优先搜索 图

题目描述

✅ 面试题 04.01. 节点间通路

image-20260929105732846

题意分析

判断有向图中能否沿给定方向从 start 到达 target。只需确认存在一条路径，不要求输出路径或最短距离。图可能包含环、自环和重复边，必须避免重复展开同一节点。

解法：BFS（邻接表）

核心思路

[!blue]
从起点不断扩展出边，就能发现全部可达节点。 先把边列表转成邻接表 adj，让 adj[u] 保存所有从 u 出发能直接到达的节点；有向边只登记一个方向，不能自动补反向边。队列保存已经发现、但尚未展开出边的节点。

起点先入队并标记。每次取出一个节点，若它就是目标就返回真；否则扫描它的出边，把尚未发现的邻居标记并入队。标记必须发生在入队时，而不是等出队后才做，才能避免多个前驱或重复边把同一节点反复加入队列。

只展开一次不会漏解：无论经过哪条路径到达同一节点，它后续可走的出边都相同，第一次展开就已保留全部可能。自环和回到已发现节点的边也会被跳过，因此搜索能够结束。若目标可达，它所在路径上的节点会从起点开始依次被发现；队列耗尽仍未发现目标，就说明不存在这样的路径。

解题步骤

  1. 为所有节点建立邻接表，并按每条边的给定方向登记终点。
  2. 将 start 入队，立即标记为已发现。
  3. 取出队首，先检查是否等于 target；否则遍历其出边，将未发现节点标记并入队。
  4. 队列耗尽后返回 false。start == target 时，第一次取出起点就返回真，对应不需要经过任何边的路径。

代码实现

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        List<Integer>[] adj = new List[n];

        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int[] e : graph) {
            // 有向关系只登记起点到终点，不补反向边。
            adj[e[0]].add(e[1]);
        }

        boolean[] visited = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            if (node == target) {
                return true;
            }

            for (int next : adj[node]) {
                if (!visited[next]) {
                    // 入队时就标记，重复边和多条路径不会反复安排同一节点。
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }

        return false;
    }
}

func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
    adj := make([][]int, n)
    for _, e := range graph {
        // 有向关系只登记起点到终点，不补反向边。
        adj[e[0]] = append(adj[e[0]], e[1])
    }

    visited := make([]bool, n)
    queue := []int{
        start,
    }
    visited[start] = true

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node == target {
            return true
        }
        for _, next := range adj[node] {
            if !visited[next] {
                // 入队时就标记，重复边和多条路径不会反复安排同一节点。
                visited[next] = true
                queue = append(queue, next)
            }
        }
    }
    return false
}

复杂度分析

  • 时间复杂度：$O(V+E)$，其中 $V$ 为节点数、$E$ 为输入边数。建图扫描每条边，搜索时每个节点最多出队一次、每条出边最多检查一次；重复边也计入 $E$。
  • 空间复杂度：$O(V+E)$，用于邻接表、访问记录和队列。

关键点总结

[!green]

  • 只建立输入给出的方向，不自动补反向边。
  • 入队即标记，将重复到达聚合为同一个状态。
  • 起点在出队时检查，自然覆盖 start=target。

易错点总结

[!yellow]

  • 把有向边当成无向边：增加题目中不存在的路径。
  • 没有访问标记：环可能造成无限扩展。
  • Java 邻接数组元素未创建列表：添加第一条边时访问空引用。
  • 队首先删除再读取：可能读错节点或在空队列上越界。

相似题目

题目 难度 关联与区别
841. 钥匙和房间 中等 同样从起点遍历有向可达对象，原题要求访问全部房间，本题只判断指定目标能否到达。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/52156872
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！