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 source to vertex destination.
Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.
Examples:
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
Here is the implementation:
from typing import List
from collections import defaultdict
def valid_path(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = set()
def dfs(node):
# print(node)
if node == destination:
return True
seen.add(node)
for n in graph[node]:
if n not in seen:
if dfs(n):
return True
return False
return dfs(source)
To run an example:
n = 3
edges = [[0, 1], [1, 2], [2, 0]]
source = 0
destination = 2
valid_path(n, edges, source, destination)## True
The time complexity of this solution is \(O(V + E)\).
The above approach uses recursion and hence it might create a very deep stack. To avoid this issue, we can use iterative DFS, which:
Avoids recursion depth issues by replacing recursive calls with an explicit stack. This ensures the function can handle larger graphs without stack overflow errors.
Neighbors are directly appended to the stack if they are not visited, avoiding nested function calls.
As soon as the destination node is found, the traversal stops, saving unnecessary computations.
def valid_path(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
# Use an iterative DFS to avoid recursion depth issues
stack = [source]
seen = set()
while stack:
node = stack.pop()
if node == destination:
return True
if node not in seen:
seen.add(node)
for neighbor in graph[node]:
if neighbor not in seen:
stack.append(neighbor)
return False
Finally, an alternative, better approach is to use Breath First Search (BFS). For this problem, BFS is better than DFS because:
from queue import deque
def valid_path(n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# Build the adjacency list for the graph
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
# Use a queue for BFS traversal
queue = deque([source])
seen = set()
while queue:
node = queue.popleft()
if node == destination:
return True
if node not in seen:
seen.add(node)
# Add neighbors to the queue
for neighbor in graph[node]:
if neighbor not in seen:
queue.append(neighbor)
return False
Note that the time complexity (worst case) does not change between approaches, but the average case becomes much faster as we move from DFS to BFS in this case.
union-find, but this solution is out of the scope of this problem for data scientists.