#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]; }}

每个人在他的人生发轫之初,总有一段时光,

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

相关文章:

你感兴趣的文章:

标签云: