Sponsored
Sponsored
The DFS approach involves exploring as far as possible along each branch before backing up. Start from the source vertex and explore each adjacent vertex, marking visited vertices. If you reach the destination during your exploration, return true. If no path to destination is found by the time all possible vertices are visited, return false.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges, due to the need to traverse the entire graph in the worst case.
Space Complexity: O(V + E) for storing the adjacency list and the visited array.
1def validPath(n, edges, source, destination):
2 if source == destination:
3 return True
4
5 from collections import defaultdict
6
7 graph = defaultdict(list)
8 for u, v in edges:
9 graph[u].append(v)
10 graph[v].append(u)
11
12 visited = set()
13
14 def dfs(node):
15 if node == destination:
16 return True
17 if node in visited:
18 return False
19
20 visited.add(node)
21
22 for neighbor in graph[node]:
23 if dfs(neighbor):
24 return True
25
26 return False
27
28 return dfs(source)This Python implementation uses a recursive depth-first search, utilizing a set to track visited nodes to avoid cycles and repeated visits. The adjacency list structure is used for graph representation. The dfs function attempts to find a path from source to destination, returning True if successful.
The Union-Find approach is effective for problems involving connectivity checks among different components. This data structure helps efficiently merge sets of connected components and determine whether two vertices are in the same connected component by checking if they share the same root. Initialize each vertex as its own component, then loop through the edges to perform union operations, connecting the components. Finally, check if the source and destination vertices belong to the same component.
Time Complexity: O(Eα(V)), where α is the Inverse Ackermann function which grows very slowly. Equivalent to O(E) practically.
Space Complexity: O(V) for storing parent and rank arrays.
This implementation in Python constructs a Union-Find set to help manage disjoint connectivity among graph nodes. It applies path compression in the `find` method, improving search efficiency, and utilizes union by rank for optimal tree height. This approach efficiently manages connectivity status, ensuring two points share connectivity status determined by their root nodes.