Find if Path Exists in Graph - LeetCode There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex start to vertex end. Given edges and the integers n, start, and end, return true__ if there is a **valid path** from __start__ to __end__, or __false__ otherwise____.__
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2
- code DFS recursion
class Solution:
def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:
if not edges: return start == end
adj = [[] for _ in range(n)]
for v, e in edges:
adj[v].append(e)
adj[e].append(v)
def dfs(v):
if v == end:
return True
while adj[v]:
if dfs(adj[v].pop()):
return True
return False
return dfs(start)
- code DFS, while loop
class Solution:
def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:
adja = [[] for i in range(n)]
for i, j in edges:
adja[i].append(j)
adja[j].append(i)
stack = [start]
visited = set(stack)
while stack:
cur = stack.pop()
if cur == end:
return True
for nei in adja[cur]:
if nei not in visited:
stack.append(nei)
visited.add(nei)
return False