Union-Find in Action: Detecting Cycles in a Graph

Picture the Union-Find algorithm as a detective looking for hidden cycles within a network of interconnected nodes. Let's walk through a real-world example to see how this algorithm can unveil cycles in a graph.

The Game Plan: Three Simple Steps

Imagine a graph as a city where each intersection is a node and each road between them is an edge. The algorithm works through three basic steps:

1. Initialize - The Starting Point:

   • What it Does: Each intersection or vertex starts off as its own isolated "neighborhood."
   • Example: Think of each vertex as its own little cul-de-sac at the beginning.

2. Union - Building Roads:

   • What it Does: Whenever you examine a road or edge (u, v), you join the neighborhoods of u and v into a larger one.
   • Example: If there's a road from Main St. (u) to Elm St. (v), you'd combine these two streets into one neighborhood.

3. Detect Cycle - The Moment of Truth:

   • What it Does: While examining a road, if you discover that both intersections are already part of the same neighborhood, you've found a cycle!
   • Example: If you're looking at a road between Park Ave. (u) and Elm St. (v), and realize they're already in the same neighborhood, then you've detected a cycle.

Walking Through the Pseudocode

Let's break down the pseudocode, imagining that:

1. E is the set of all roads or edges.
2. u and v are individual intersections or vertices.
3. X and Y are neighborhoods or subsets that u and v belong to, respectively.

1for each unvisited road (u,v) in E {
2    If the neighborhood of u is the same as that of v {
3        # They're already in the same neighborhood!
4        Print ("Cycle detected!")
5    }
6    else {
7        # Merge the two neighborhoods into one
8        Union(X, Y)
9    }
10}

By following these steps, you can efficiently discover if any cycles exist within your graph—akin to finding a loop in our hypothetical city that takes you back to your starting point.

xxxxxxxxxx

console.log(isCycle(graph));

function find(parent, i) {

    if (parent[i] === i)

        return i;

    return find(parent, parent[i]);

}

​

function union(parent, rank, x, y) {

    let rootX = find(parent, x);

    let rootY = find(parent, y);

​

    if (rootX !== rootY) {

        if (rank[rootX] < rank[rootY])

            parent[rootX] = rootY;

        else if (rank[rootX] > rank[rootY])

            parent[rootY] = rootX;

        else {

            parent[rootY] = rootX;

            rank[rootX]++;

        }

    }

}

​

function isCycle(graph) {

    let parent = [...Array(graph.length).keys()];

    let rank = Array(graph.length).fill(0);

​

    for (let [u, v] of graph) {

        if (find(parent, u) === find(parent, v))

            return true;