Solution: Find if Path Exists in Graph

Statement

Given a 2D list, edges,  which represents a bidirectional graph. Each vertex is labeled from $0$ to $n-1$, and each edge in the graph is represented as a pair, $[x_i, y_i]$, showing a bidirectional edge between $x_i$ and $y_i$. Each pair of vertices is connected by at most one edge, and no vertex is connected to itself.

Determine whether a valid path exists from the source vertex to the destination vertex. If it exists, return TRUE; otherwise, return FALSE.

Constraints:

• $1\leq$ n $\leq 10^2$

• $0 \leq$ edges.length $\leq n(n-1)/2$

• edges[i].length $= 2$

• $0 \leq x_i,y_i \leq n-1$

• $x_i\ne y_i$

• $0\leq$ source, destination $\leq n - 1$

• There are no duplicate edges.

• There are no self-edges.

Solution

This solution uses the union-find algorithm to find if there exists any path between two nodes in a graph.

The Union function merges two nodes by connecting their roots for each edge in the graph. A rank system is used, where each node initially is its parent and is given a rank of $1$, meaning it’s a tree with just one node. When two nodes are merged, the Union operation compares the ranks of the roots of the two nodes. The rank is updated by attaching the tree with the smaller rank under the tree with the larger rank. If both trees have the same rank, one tree becomes a subtree of the other, and the rank of the new root is increased by $1$.

After going through all the edges, the Find function checks if the source and destination nodes belong to the same group by looking for their roots. If a node isn’t its root, the find operation follows the chain of parent nodes until it finds the root.

After finding the roots, if both nodes share the same root, there will be a path between them.

Here’s the step-by-step implementation of the solution:

• Initialize a union-find object for n nodes. This creates two lists:

  • root: Each element initially is the root of itself.

  • rank: This is used to merge the smaller tree under the larger tree.

• For each edge between nodes x and y:

  • Call the Union function and find the roots of both x and y.

  • If their roots are different:

    • Compare the ranks of both roots and attach the tree with the smaller rank under the tree with the larger one.

    • Increase the rank by $1$ of the new root.

  • Do nothing if they have the same roots because no merging is required.

• After processing all the edges:

  • Check if the source and destination nodes have the same root. If they do:

    • Return TRUE because a path exists between them.

  • Otherwise, return FALSE if both belong to different roots.

Let’s look at the following illustration to get a better understanding of the solution: