节点间通路

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

示例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。
图中可能存在自环和平行边。
通过次数9,562提交次数18,034

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

class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        Map<Integer, Set<Integer>> neiTable = new HashMap<>();

        for (int i = 0; i < graph.length; i++) {
            if (graph[i][0] == graph[i][1]) continue;
            neiTable.computeIfAbsent(graph[i][0], k -> new HashSet<>()).add(graph[i][1]);
        }

        return dfs(neiTable, start, target);
    }
    public boolean dfs(Map<Integer, Set<Integer>> neiTable, int start, int target) {
        if (start == target) return true;
        for (Integer nei : neiTable.getOrDefault(start, new HashSet<>())) {
            if (dfs(neiTable, nei, target)) return true;
        }
        return false;
    }
}

参考文献

深度优先搜索作者：王小强

赏

谢谢你请我吃糖果

微信