Find if Path Exists in Graph
Easy
You are given a graph problem. Let's define the problem formally:
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] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. 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.
Example 1:
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:
- 0 → 1 → 2
- 0 → 2
Example 2:
n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.
Could you please implement a function to solve this problem efficiently? Consider edge cases and analyze the time and space complexity of your solution.
Solution
Naive Approach: Depth-First Search (DFS)
A straightforward approach is to use Depth-First Search (DFS) to explore all possible paths from the source vertex. We can mark visited nodes to avoid cycles.
- Build the Graph: Represent the graph using an adjacency list.
- DFS Traversal: Start DFS from the
sourcenode. Mark each visited node. - Check Destination: During DFS, if we encounter the
destinationnode, returntrue. If DFS finishes without finding the destination, returnfalse.
Code (Python):
def validPath_naive(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
adj_list = [[] for _ in range(n)]
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
visited = [False] * n
def dfs(node):
if node == destination:
return True
visited[node] = True
for neighbor in adj_list[node]:
if not visited[neighbor]:
if dfs(neighbor):
return True
return False
return dfs(source)
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. In the worst case, we might visit all vertices and edges.
Space Complexity: O(V + E) to store the adjacency list and O(V) for the visited array and recursion stack in the worst-case scenario (a deeply unbalanced graph).
Optimal Approach: Breadth-First Search (BFS)
BFS also guarantees to find the shortest path, although in this problem we just need to find any path. BFS can sometimes be more efficient in terms of space complexity if the graph is very wide since DFS's recursion stack can grow quite deep.
- Build the Graph: (Same as DFS - Adjacency List)
- BFS Traversal: Use a queue to perform BFS starting from the
sourcenode. Mark visited nodes. - Check Destination: If the destination is enqueued, a path exists.
Code (Python):
from collections import deque
def validPath(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
adj_list = [[] for _ in range(n)]
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
visited = [False] * n
queue = deque([source])
visited[source] = True
while queue:
node = queue.popleft()
if node == destination:
return True
for neighbor in adj_list[node]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
return False
Time Complexity: O(V + E), same as DFS.
Space Complexity: O(V + E) to store the adjacency list and O(V) for the visited array and queue.
Edge Cases
- Source == Destination: If the source and destination are the same, there's a path (return
true). - Empty Graph: If there are no edges, there's a path only if source == destination.
- Disconnected Graph: The algorithm should correctly handle disconnected graphs.
- Single Node Graph: If n == 1, there's a path only if source == destination.
