LeetCode 面试题 04.01. 节点间通路

Categories:

题目描述
思路分析
1. 解法一：广度优先搜索（推荐）
2. 解法二：深度优先搜索
相似题目

题目描述

✅ 面试题 04.01. 节点间通路

思路分析

解法一：广度优先搜索（推荐）

核心思路：

将有向图的边构建为邻接表，再以 source 为起点进行 BFS

使用队列逐层扩展，使用 visited 集合标记已访问节点避免重复

若在 BFS 过程中访问到 target，则返回 true；队列耗尽未找到则返回 false

复杂度分析：

时间复杂度：O(V + E)，其中 V 为节点数，E 为边数

空间复杂度：O(V + E)，邻接表存储图结构及 visited 集合

class Solution {

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 构建邻接表
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : graph) {
            adj.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        }

        // BFS
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == target) {
                return true;
            }
            for (int next : adj.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }
        return false;
    }
}

func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
    // 构建邻接表
    adj := make(map[int][]int)
    for _, edge := range graph {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
    }

    // BFS
    queue := []int{start}
    visited := map[int]bool{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
}

解法二：深度优先搜索

核心思路：

构建邻接表后，以 source 为起点进行 DFS 递归搜索

使用 visited 集合防止环路导致的无限递归

若当前节点等于 target 则直接返回 true

复杂度分析：

时间复杂度：O(V + E)，其中 V 为节点数，E 为边数

空间复杂度：O(V + E)，递归调用栈最深 O(V)

class Solution {

    private Map<Integer, List<Integer>> adj;
    private Set<Integer> visited;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        adj = new HashMap<>();
        visited = new HashSet<>();
        for (int[] edge : graph) {
            adj.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        }
        return dfs(start, target);
    }

    private boolean dfs(int node, int target) {
        if (node == target) {
            return true;
        }
        visited.add(node);
        for (int next : adj.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(next) && dfs(next, target)) {
                return true;
            }
        }
        return false;
    }
}

func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
    adj := make(map[int][]int)
    for _, edge := range graph {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
    }

    visited := make(map[int]bool)

    var dfs func(node int) bool
    dfs = func(node int) bool {
        if node == target {
            return true
        }
        visited[node] = true
        for _, next := range adj[node] {
            if !visited[next] && dfs(next) {
                return true
            }
        }
        return false
    }

    return dfs(start)
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	图、BFS/DFS
547. 省份数量	中等	图、并查集
797. 所有可能的路径	中等	图、DFS
1971. 寻找图中是否存在路径	简单	图、BFS/DFS
207. 课程表	中等	有向图、拓扑排序
417. 太平洋大西洋水流问题	中等	图、BFS/DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/52156872