class Solution {
public:
bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
}
};
面试题 04.01. 节点间通路
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例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
提示：
原站题解
javascript 解法, 执行用时: 312 ms, 内存消耗: 86.6 MB, 提交时间: 2022-11-30 21:25:12
/**
* @param {number} n
* @param {number[][]} graph
* @param {number} start
* @param {number} target
* @return {boolean}
*/
var findWhetherExistsPath = (n, graph, start, target) => {
// 将连接关系放在数组中
const set = new Array(n).fill(0).map(() => new Set());
// 数组index对应起点
// 每个数组元素是set，set里面的值是index指向的终点
for (const [start, end] of graph) {
set[start].add(end);
}
const visited = new Set();
const dfs = start => {
// 到达终点，返回true
if (start === target) return true;
// 如果当前起点已经访问过，还没有true，说明成环了，返回false
if (visited.has(start)) return false;
// 标记访问
visited.add(start);
// 遍历当前点的每个终点
for (const newStart of set[start]) {
if (dfs(newStart)) return true;
}
return false;
};
return dfs(start);
};
javascript 解法, 执行用时: 132 ms, 内存消耗: 70.1 MB, 提交时间: 2022-11-30 21:24:37
/**
* @param {number} n
* @param {number[][]} graph
* @param {number} start
* @param {number} target
* @return {boolean}
*/
var findWhetherExistsPath = function (n, graph, start, target) {
if (start === target) return true;
const set = new Set([start]);
let count = 1;
while (true) {
for (const item of graph) {
if (set.has(item[0])) {
if (item[1] === target) return true;
set.add(item[1])
}
}
if (set.size > count) {
count = set.size;
} else {
return false;
}
}
};
golang 解法, 执行用时: 124 ms, 内存消耗: 22 MB, 提交时间: 2022-11-30 21:23:33
func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
g := make([][]int, n)
for i:=0; i<n; i++ {
g[i] = []int{}
}
for i:=0; i<len(graph); i++ {
from, to := graph[i][0], graph[i][1]
g[from] = append(g[from], to)
}
return traverse(g, start, target)
}
func traverse(g [][]int, start, target int) bool {
for _, nxt := range g[start] {
if nxt == target {
return true
}
res := traverse(g, nxt, target)
if res {
return true
}
}
return false
}
golang 解法, 执行用时: 148 ms, 内存消耗: 25.9 MB, 提交时间: 2022-11-30 21:23:16
func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
edges := make([][]int,n)
Flag := make([]int,n)
for i:=0;i<len(graph);i++{
edges[graph[i][0]] = append(edges[graph[i][0]],graph[i][1])
}
queue := make([]int,0)
queue = append(queue,start)
for len(queue) > 0{
tmp := queue[0]
queue = queue[1:]
Flag[tmp] = 1
if tmp == target{
return true
}
for i:=0;i<len(edges[tmp]);i++{
if Flag[edges[tmp][i]] == 0{
queue = append(queue,edges[tmp][i])
}
}
}
return false
}
golang 解法, 执行用时: 156 ms, 内存消耗: 25.2 MB, 提交时间: 2022-11-30 21:22:44
func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
// 图中可能存在自环和平行边
g := make([]map[int]bool, n)
for i := 0; i < n; i++ {
g[i] = make(map[int]bool)
}
for _, edge := range graph {
if edge[0] != edge[1] {
g[edge[0]][edge[1]] = true
}
}
// bfs
q := make([]int, 1)
q[0] = start
visit := make([]bool, n)
for len(q) > 0 {
cur := q[0]
q = q[1:]
if visit[cur] {
continue
}
visit[cur] = true
if cur == target {
return true
}
for k, _ := range g[cur] {
if !visit[k] {
q = append(q, k)
}
}
}
return false
}
python3 解法, 执行用时: 172 ms, 内存消耗: 48.8 MB, 提交时间: 2022-11-30 21:22:02
from collections import defaultdict
class Solution:
def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
hashMap = defaultdict(set)
for key, value in graph: # 用字典来构建邻接表
hashMap[key].add(value)
def dfs(start, target, visited):
if start == target:
return True
if visited[start]:
return False
visited[start] = True
flag = False # 代表当前路径有没有找到target
if start in hashMap:
for cur in hashMap[start]:
flag = flag or dfs(cur, target, visited) # 这里用or连接，代表只要有一条路径能指向target就可以
return flag
visited = [False] * n
return dfs(start, target, visited)
python3 解法, 执行用时: 168 ms, 内存消耗: 52.1 MB, 提交时间: 2022-11-30 21:20:19
from collections import defaultdict
class Solution:
def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
dic = collections.defaultdict(list)
# 建立图
for u, v in graph:
dic[u].append(v)
# 记录访问过的节点
vis = set()
q = deque()
q.append(start)
# BFS
while q:
pos = q.popleft()
if pos == target:
return True
for nxt in dic[pos]:
if nxt not in vis:
vis.add(nxt)
q.append(nxt)
return False