Given a directed graph with n vertices and two vertices source and destination, check whether there is a path from the source vertex to the destination vertex.
The graph is represented as an adjacency list where graph[i] contains all vertices that vertex i has directed edges to.
Return true if there is a valid directed path from source to destination, false otherwise.
Input: n =4, edges =[[0,1],[2,3]], source =0, destination =3Output: falseExplanation: There is no path from vertex 0 to vertex 3. They are in different components.
Input: n =3, edges =[[0,1],[1,2],[2,0]], source =1, destination =0Output: trueExplanation: There is a cycle, and vertex 0is reachable from vertex 1:1→2→0
This problem is similar to Find if Path Exists in Graph, but here the graph is directed (uni-directional) whereas there it is undirected (bi-directional).
Use DFS to traverse the directed graph starting from the source vertex. If we can reach the destination vertex during traversal, return true. Use a visited set to avoid cycles.
from collections import defaultdict
from typing import List, Set, Dict
classSolution:
defvalidPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
if source == destination:
returnTrue# Build directed adjacency list graph: Dict[int, List[int]] = defaultdict(list)
for u, v in edges:
graph[u].append(v)
visited: Set[int] = set()
return self.dfs(graph, source, destination, visited)
defdfs(self, graph: Dict[int, List[int]], current: int,
destination: int, visited: Set[int]) -> bool:
if current == destination:
returnTrueif current in visited:
returnFalse visited.add(current)
for neighbor in graph[current]:
if self.dfs(graph, neighbor, destination, visited):
returnTruereturnFalse# Alternative iterative DFS implementationclassSolutionIterative:
defvalidPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
if source == destination:
returnTrue# Build directed adjacency list graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
stack = [source]
visited = set()
while stack:
current = stack.pop()
if current == destination:
returnTrueif current in visited:
continue visited.add(current)
for neighbor in graph[current]:
if neighbor notin visited:
stack.append(neighbor)
returnFalse
from collections import deque, defaultdict
from typing import List
classSolution:
defvalidPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
if source == destination:
returnTrue# Build directed adjacency list graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
queue = deque([source])
visited = {source}
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if neighbor == destination:
returnTrueif neighbor notin visited:
visited.add(neighbor)
queue.append(neighbor)
returnFalse
Cycle handling: Directed cycles don’t affect the algorithm complexity
When to use each approach:
Use DFS when you want to explore deeply and memory is a concern
Use BFS when you want to find the shortest path or explore systematically
Both approaches have the same time and space complexity for this problem, so the choice often comes down to personal preference or specific requirements.