1971. Find if Path Exists in Graph

EasyDepth-First SearchBreadth-First SearchUnion FindGraph

Problem Description

In this problem, we are given a bi-directional graph consisting of n vertices, labeled from 0 to n - 1. The connections or edges between these vertices are provided in the form of a 2D array called edges, where each element of the array represents an edge connecting two vertices. For example, if edges[i] = [u, v], there is an edge connecting vertex u to vertex v and vice versa since the graph is bi-directional. It's also specified that each pair of vertices can be connected by at most one edge and that no vertex is connected to itself with an edge.

Our goal is to find out if there exists a path from a given source vertex to a destination vertex. If such a path exists, the function should return true; otherwise, it should return false.

Flowchart Walkthrough

Let's analyze the problem on leetcode 1971. Find if Path Exists in Graph using the Flowchart. Here's a step-by-step process to determine the right algorithm to use:

Is it a graph?

Yes: The problem directly describes it as a graph where we need to find if a path exists between two vertices.

Is it a tree?

No: The graph described could contain cycles and may not have hierarchical parent-child relationships typical of trees.

Is the problem related to directed acyclic graphs (DAGs)?

No: The problem does not specify that the graph is acyclic, nor does it focus on issues specific to DAGs such as topological sorting.

Is the problem related to shortest paths?

No: The task is to find if a path exists at all, not the shortest path.

Does the problem involve connectivity?

Yes: The core of the problem is to find out whether there is a connection (path) between two nodes.

Is the graph weighted?

No: The problem does not mention any weights associated with the edges, focusing simply on the existence of paths.

Conclusion: According to the flowchart and the problem's focus on unweighted connectivity, the ideal algorithms to consider are BFS or DFS. For this setting, using the Depth-First Search (DFS) pattern is a suitable choice to explore the connectivity between nodes.

Intuition

The intuitive approach to determine if a valid path exists between two vertices in a graph is by using graph traversal methods such as Depth-First Search (DFS) or Breadth-First Search (BFS). These methods can explore the graph starting from the source vertex and check if the destination vertex can be reached.

However, the solution provided uses a different approach known as Disjoint Set Union (DSU) or Union-Find algorithm, which is an efficient algorithm to check whether two elements belong to the same set or not. In the context of graphs, it helps determine if two vertices are in the same connected component, i.e., if there is a path between them.

The Union-Find algorithm maintains an array p where p[x] represents the parent or the representative of the set to which x belongs. In the given solution, the find function is a recursive function that finds the representative of a given vertex x. If x is the representative of its set, it returns x itself; otherwise, it recursively calls itself to find x's representative and performs path compression along the way. Path compression is an optimization that flattens the structure of the tree by making every node directly point to the representative of the set, which speeds up future operations.

Then, in the solution, every edge [u, v] is considered, and the vertices u and v are united by setting their representatives to be the same. In the end, it checks whether the source and the destination vertices have the same representative. If they do, it means they are connected, and thus, a valid path exists between them, returning true; else, it returns false.

By using Union-Find, we can avoid the need to explicitly traverse the graph while still being able to determine connectivity between vertices efficiently.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution provided employs the Union-Find (Disjoint Set Union) algorithm. The implementation of this algorithm consists of two main operations: find and union. In the context of the problem, Union-Find helps to efficiently check if there is a path between two vertices in the graph.

The algorithm uses an array named p where p[i], initially, is set to i for all vertices 0 to n-1. This step constitutes the make-set operation where each vertex is initially the parent of itself, meaning each vertex starts in its own set.

The find function is then defined. This function takes an integer x, which represents a vertex, and it recursively finds the representative (parent) of the set that x belongs to. This is done by checking if p[x] is equal to x. If p[x] != x, then x is not the representative of its set, so the function is called recursively with p[x]. During recursion, path compression is performed by setting p[x] = find(p[x]). Path compression is a crucial optimization as it helps to reduce the time complexity significantly by flattening the structure of the tree.

Next, a loop iterates over each edge in the edges list. For each edge [u, v], the union operation is performed implicitly by setting p[find(u)] = find(v). This essentially connects the two vertices u and v by ensuring they have the same representative. By performing this operation for all edges in the graph, all connected components in the graph are merged.

Finally, the solution checks whether there is a valid path between source and destination. This is done by comparing their representatives: if find(source) == find(destination), then source and destination are in the same connected component, signifying that there is a path between them, and hence true is returned. If the representatives are different, the function returns false, implying there is no valid path.

It is worth noting that the Union-Find algorithm is particularly effective for problems involving connectivity queries in a static graph, where the graph does not change over time. This algorithm allows such queries to be performed in nearly constant time, making it a powerful tool for solving such problems.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small graph with 5 vertices (n = 5) labeled from 0 to 4.

The edges array is provided as follows:

edges = [[0, 1], [1, 2], [3, 4]]

Our goal is to determine if there is a path between the source vertex 0 and the destination vertex 3. From the edges given, we can visualize the graph:

0 --- 1 --- 2

3 --- 4

We would use the Union-Find algorithm for this.

Initially, all vertices are their own parents:

p = [0, 1, 2, 3, 4]

We start by uniting the vertices that have an edge between them using the union operation.

Union operation on edge [0, 1]: set the parent of the representative of 1 (p[1]) to be the representative of 0 (p[0]). Hence, p[1] = 0.

After step 1, our updated p array is:

p = [0, 0, 2, 3, 4]

Union operation on edge [1, 2]: set the parent of the representative of 2 (p[2]) to be the representative of 1 (which was set to 0 previously). Hence, p[2] = 0.

After step 2, our updated p array is:

p = [0, 0, 0, 3, 4]

Union operation on edge [3, 4]: set the parent of the representative of 4 (p[4]) to be the representative of 3 (p[3]). Hence, p[4] = 3.

After step 3, our updated p array is:

p = [0, 0, 0, 3, 3]

Now we check if there is a valid path between the source vertex 0 and the destination vertex 3 by comparing their representatives.

Find the representative of the source vertex 0:

find(0) will return 0 since p[0] is 0.

Find the representative of the destination vertex 3:

find(3) will return 3 since p[3] is 3.

Since the representatives of vertex 0 and vertex 3 are different (0 is not equal to 3), we conclude there is no path between them, and the function should return false.

It is evident from the p array and the disconnected components in the graph visualization that vertices 0, 1, and 2 are in one connected component, and vertices 3 and 4 form another component. There's no edge that connects these two components, confirming our conclusion.

Solution Implementation

1from typing import List
2
3class Solution:
4    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
5        # Helper function to find the root of a node 'x' in the disjoint set.
6        # It also applies path compression to optimize future lookups.
7        def find_root(node: int) -> int:
8            if parent[node] != node:
9                parent[node] = find_root(parent[node])
10            return parent[node]
11      
12        # Initialize parent pointers for each node to point to itself.
13        parent = list(range(n))
14      
15        # Iterate through each edge and perform union operation.
16        for start_node, end_node in edges:
17            # Union the sets by updating the root of one to the root of the other.
18            parent[find_root(start_node)] = find_root(end_node)
19      
20        # Check if the source and destination are in the same set.
21        # If the find_root of both is the same, they are connected.
22        return find_root(source) == find_root(destination)
23

1class Solution {
2    // Parent array that stores the root of each node's tree in the disjoint set forest
3    private int[] parent;
4
5    // Method to determine if there is a valid path between the source and the destination nodes within an undirected graph
6    public boolean validPath(int n, int[][] edges, int source, int destination) {
7        // Initialize the parent array where each node is initially its own parent (representative of its own set)
8        parent = new int[n];
9        for (int i = 0; i < n; ++i) {
10            parent[i] = i;
11        }
12      
13        // Union operation: merge the sets containing the two nodes of each edge
14        for (int[] edge : edges) {
15            parent[find(edge[0])] = find(edge[1]);
16        }
17      
18        // If the source and destination nodes have the same parent/root, they are connected; otherwise, they are not
19        return find(source) == find(destination);
20    }
21
22    // Method to find the root of the set that contains node x utilizing path compression for efficiency
23    private int find(int x) {
24        if (parent[x] != x) { // If x is not its own parent, it's not the representative of its set
25            parent[x] = find(parent[x]); // Recurse to find the root of the set and apply path compression
26        }
27        return parent[x]; // Return the root of the set that contains x
28    }
29}
30

1class Solution {
2public:
3    // Parent vector to represent the disjoint set (union-find) structure
4    vector<int> parent;
5
6    // Main function to check if there is a valid path between source and destination
7    // Parameters:
8    // n - number of vertices
9    // edges - list of edges represented as pairs of vertices
10    // source - starting vertex
11    // destination - ending vertex
12    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
13        // Initialize parent array so that each vertex is its own parent initially
14        parent.resize(n);
15        for (int i = 0; i < n; ++i)
16            parent[i] = i;
17
18        // Iterate through all edges to perform the union operation
19        for (auto& edge : edges)
20            unionSet(find(edge[0]), find(edge[1]));
21
22        // Check if the source and destination have the same root parent
23        // If they do, there is a valid path between them
24        return find(source) == find(destination);
25    }
26
27    // Helper function to find the root parent of a vertex x
28    int find(int x) {
29        // Path Compression: Recursively makes the parents of the vertices
30        // along the path from x to its root parent point directly to the root parent
31        if (parent[x] != x)
32            parent[x] = find(parent[x]);
33        return parent[x];
34    }
35
36    // Helper function to perform the union operation on two subsets
37    void unionSet(int x, int y) {
38        // Find the root parents of the vertices
39        int rootX = find(x);
40        int rootY = find(y);
41      
42        // Union by setting the parent of rootX to rootY
43        if (rootX != rootY)
44            parent[rootX] = rootY;
45    }
46};
47

1// Global parent array to represent the disjoint set (union-find) structure
2const parent: number[] = [];
3
4// Function to initialize the parent array with each vertex as its own parent
5function initializeParent(n: number): void {
6    for (let i = 0; i < n; i++) {
7        parent[i] = i;
8    }
9}
10
11// Function to find the root parent of a vertex 'x' using path compression
12function find(x: number): number {
13    if (parent[x] !== x) {
14        parent[x] = find(parent[x]);
15    }
16    return parent[x];
17}
18
19// Function to perform the union operation on two subsets
20function unionSet(x: number, y: number): void {
21    const rootX = find(x);
22    const rootY = find(y);
23
24    if (rootX !== rootY) {
25        parent[rootX] = rootY;
26    }
27}
28
29// Main function to check if there is a valid path between 'source' and 'destination'
30function validPath(n: number, edges: number[][], source: number, destination: number): boolean {
31    initializeParent(n);
32
33    // Perform the union operation for each edge to connect the vertices in the union-find structure
34    for (const edge of edges) {
35        unionSet(find(edge[0]), find(edge[1]));
36    }
37
38    // If the source and destination have the same root parent, a valid path exists
39    return find(source) === find(destination);
40}
41

Time and Space Complexity

The given Python code represents a solution to check if there's a valid path between the source and destination nodes in an undirected graph. The code utilizes the Union-Find algorithm, also known as the Disjoint Set Union (DSU) data structure.

Time Complexity:

The time complexity of this algorithm can be considered as O(E * α(N)) for the Union-Find operations, where E is the number of edges and α(N) is the Inverse Ackermann function which grows very slowly and is nearly constant for all practical values of N. The reason for this time complexity is that each union operation, which combines the sets containing u and v, and each find operation, which finds the root of the set containing a particular element, takes α(N) time on average.

The find function uses path compression which flattens the structure of the tree by making every node point to the root whenever find is used on it. Because of path compression, the average time complexity of find, and thus the union operation which uses find, becomes nearly constant.

Given that there are E iterations to process the edges array, the time complexity of the for loop would be O(E * α(N)). Additionally, there are two more find operations after the for loop, but these do not significantly affect the overall time complexity, as they also work in α(N) time.

Space Complexity:

The space complexity of the code is O(N), where N is the number of nodes in the graph. This is because we maintain an array p that holds the representative (parent) for each node, and it's of size equal to the number of nodes.

Therefore, the space complexity of maintaining this array is linear with respect to the number of nodes.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know