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 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:
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: - 0 → 1 → 2 - 0 → 2
Example 2:
Input: 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.
Constraints:
1 <= n <= 2 * 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ui, vi <= n - 1ui != vi0 <= source, destination <= n - 1Problem Overview: You are given an undirected graph with n nodes and a list of edges. The task is simple: determine whether a valid path exists between a given source node and a destination node. In other words, check if the two nodes belong to the same connected component in the graph.
Approach 1: Depth-First Search (DFS) Traversal (Time: O(V + E), Space: O(V))
The most direct solution treats the graph as an adjacency list and performs a traversal starting from the source. Using Depth-First Search, you recursively explore all neighbors of each node until either the destination is found or all reachable nodes are visited. A visited array prevents revisiting nodes and getting stuck in cycles. If the traversal ever reaches the destination, a path exists.
This works because DFS explores every vertex reachable from the starting node. If the destination belongs to the same connected component, DFS will eventually reach it. Building the adjacency list takes O(E) time, and the traversal visits each node and edge at most once. This approach is intuitive and commonly used for connectivity checks in a graph.
Many implementations also use Breadth-First Search instead of DFS. BFS uses a queue instead of recursion but has the same time complexity O(V + E) and space complexity O(V). Both approaches work equally well for reachability problems.
Approach 2: Union-Find (Disjoint Set Union) (Time: O(E · α(V)), Space: O(V))
Union-Find models the graph as a collection of connected components. Initially, each node belongs to its own set. For every edge (u, v), perform a union operation to merge the sets containing those nodes. After processing all edges, nodes that are connected by any path will belong to the same root set.
To check if a path exists, simply compare the roots of source and destination. If they share the same representative parent, they are connected. With path compression and union by rank, each operation runs in nearly constant time, represented as the inverse Ackermann function α(V).
This approach avoids explicit traversal and is extremely efficient when you need to process many connectivity queries or build components incrementally. It’s a classic use case of the Union-Find data structure.
Recommended for interviews: DFS or BFS is typically the expected solution because it directly demonstrates graph traversal skills and understanding of connected components. Union-Find is also highly valued, especially if the interviewer wants to test knowledge of disjoint-set data structures. Showing DFS first proves you understand graph traversal fundamentals, while mentioning Union-Find demonstrates deeper algorithmic knowledge.
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.
This C implementation of the DFS approach creates an adjacency list from the given edge list. It uses a recursive depth-first search to explore the graph, marking nodes as visited. The search begins at the source and continues until it either finds the destination or runs out of vertices to explore. If the destination is found, the function returns true; otherwise, it returns false. The adjacency list is implemented with dynamic memory allocation to store neighboring vertices efficiently.
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.
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.
This C code implements the Union-Find data structure with path compression and union by rank. Initially, each node is its own parent. The `find` function implements path compression to flatten the structure for efficient look-up, while the `unionSets` function connects components, using rank optimization to keep the tree flat. After processing all edges, the function performs a final check to see if the source and destination belong to the same connected 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.
We first convert edges into an adjacency list g, then use DFS to determine whether there is a path from source to destination.
During the process, we use an array vis to record the vertices that have already been visited to avoid revisiting them.
The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of nodes and edges, respectively.
We can also use BFS to determine whether there is a path from source to destination.
Specifically, we define a queue q, initially adding source to the queue. Additionally, we use a set vis to record the vertices that have already been visited to avoid revisiting them.
Next, we continuously take vertices i from the queue. If i = destination, it means there is a path from source to destination, and we return true. Otherwise, we traverse all adjacent vertices j of i. If j has not been visited, we add j to the queue q and mark j as visited.
Finally, if the queue is empty, it means there is no path from source to destination, and we return false.
The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of nodes and edges, respectively.
Union-Find is a tree-like data structure that, as the name suggests, is used to handle some disjoint set merge and query problems. It supports two operations:
O(\alpha(n)).O(\alpha(n)).For this problem, we can use the Union-Find set to merge the edges in edges, and then determine whether source and destination are in the same set.
The time complexity is O(n log n + m) or O(n \alpha(n) + m), and the space complexity is O(n). Where n and m are the number of nodes and edges, respectively.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) | 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. |
| Union-Find (Disjoint Set Union, DSU) | 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. |
| DFS | — |
| BFS | — |
| Union-Find | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(V + E) | O(V) | Best general approach for checking connectivity using graph traversal |
| Breadth-First Search (BFS) | O(V + E) | O(V) | Preferred when iterative traversal with a queue is easier than recursion |
| Union-Find (Disjoint Set Union) | O(E · α(V)) | O(V) | Efficient for connectivity checks when processing many edges or multiple queries |
Find if Path Exists in Graph - Leetcode 1971 - Graphs (Python) • Greg Hogg • 26,125 views views
Watch 9 more video solutions →Practice Find if Path Exists in Graph with our built-in code editor and test cases.
Practice on FleetCode