Detect Cycle in Undirected Graph (Union-Find)

Welcome to a deep dive into one of the most fascinating topics in computer science - Detecting Cycles in Undirected Graphs using the Union-Find data structure! 🎯

By the end of this lesson, you'll not only understand how to detect cycles in undirected graphs but also learn about the Union-Find data structure, which is a powerful tool in graph theory. Let's embark on this exciting journey!

Understanding Graphs and Union-Find 📝

Before diving into the main topic, let's quickly revise what graphs are and introduce the Union-Find data structure.

Graphs

A graph is a collection of nodes (also known as vertices) and edges that connect them. In an undirected graph, edges connect nodes in both directions.

Union-Find Data Structure

The Union-Find data structure is a powerful tool used to represent a set of disjoint sets efficiently. It helps in finding the set a given element belongs to, merging two sets, and determining if two sets are the same.

Detecting Cycles in Undirected Graphs 💡

Now, let's focus on detecting cycles in undirected graphs using the Union-Find data structure.

The Idea

The basic idea is to use the Union-Find data structure to represent the connected components of the graph. If, during the traversal of the graph, we find a situation where merging two components results in the same set, it implies the presence of a cycle.

Implementation

Here's a simple implementation of the cycle detection algorithm using the Union-Find data structure in Python:

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.rank[root_x] += self.rank[root_y]
        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += self.rank[root_x]

        return True

# Example Graph
edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4)]

# Initialize Union-Find data structure
uf = UnionFind(5)

# Loop through the edges and try to merge the sets
for x, y in edges:
    if not uf.union(x, y):
        print("Cycle detected!")
        break

# If we reach here, no cycle was detected
print("No cycle found.")

In this example, we create an undirected graph with 5 vertices and 4 edges. The UnionFind class represents the Union-Find data structure. We then loop through the edges, trying to merge the sets for each edge. If merging two sets fails (i.e., they already belong to the same set), we detect a cycle and break the loop.

💡 Pro Tip:

Keep in mind that the Union-Find data structure is not only useful for detecting cycles in undirected graphs but can also be used for many other problems related to graphs, such as finding the smallest set of representatives in a partition, determining if two graphs are isomorphic, and more.

Detect Cycle in Undirected Graph (Union-Find)

Detect Cycle in Undirected Graph (Union-Find)

Understanding Graphs and Union-Find 📝

Graphs

Union-Find Data Structure

Detecting Cycles in Undirected Graphs 💡

The Idea

Implementation

💡 Pro Tip:

Quiz