#yyds干货盘点# LeetCode程序员面试金典：节点间通路

题目：

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

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

代码实现：

class Solution { public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { Set<Integer>[] adjacentArr = new Set[n]; for (int i = 0; i < n; i++) { adjacentArr[i] = new HashSet<Integer>(); } for (int[] edge : graph) { if (edge[0] != edge[1]) { adjacentArr[edge[0]].add(edge[1]); } } boolean[] visited = new boolean[n]; visited[start] = true; Queue<Integer> queue = new ArrayDeque<Integer>(); queue.offer(start); while (!queue.isEmpty() && !visited[target]) { int vertex = queue.poll(); Set<Integer> adjacent = adjacentArr[vertex]; for (int next : adjacent) { if (!visited[next]) { visited[next] = true; queue.offer(next); } } } return visited[target]; }}