DSU Applications 🎯

Welcome to our comprehensive guide on Disjoint Set Union (DSU) Applications! In this lesson, we'll explore the practical applications of DSU in solving various real-world problems.

What is Disjoint Set Union (DSU)? 📝

Before we dive into the applications, let's quickly recap what DSU is: DSU is a data structure used to efficiently maintain a partition of a set into disjoint subsets of elements such that all elements in the same subset are in the same connected component and all elements in different subsets are in different connected components.

DSU Applications 💡

Minimum Spanning Tree (MST) 💡

One of the most common applications of DSU is in finding the Minimum Spanning Tree (MST) of a graph. MST is a tree that spans all vertices in the graph and has the minimum possible total edge weight.

Here's a simple example of Kruskal's algorithm, which uses DSU to find the MST of a graph:

python

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

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return
        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootX] = rootY
            self.rank[rootY] += self.rank[rootX]

# Example graph edges
edges = [(0, 1, 5), (0, 7, 3), (1, 2, 6), (1, 7, 2), (2, 3, 7), (2, 6, 8), (3, 4, 9), (4, 5, 10), (5, 6, 11), (6, 7, 4)]

# Sort the edges in increasing order of weight
edges.sort(key=lambda edge: edge[2])

graph = DisjointSet(8)
mst = []

for edge in edges:
    x, y, weight = edge
    if graph.find(x) != graph.find(y):
        graph.union(x, y)
        mst.append(edge)
        # Print the MST edges for better understanding
        print(f'Edge {x} - {y} with weight {weight} added to MST')

Union Find Algorithms Quiz 💡

Depth-First Search (DFS) and Topological Sorting 💡

DSU can also be used to perform Depth-First Search (DFS) and Topological Sorting on a directed acyclic graph (DAG). DFS helps explore and traverse the graph, while Topological Sorting arranges the vertices in a linear sequence that follows the directed edges from the graph.

python

class DisjointSet:
    # ... (Same as previous example)

    def dfs(self, node, visited, stack):
        visited[node] = True
        for neighbor in self.neighbors(node):
            if not visited[neighbor]:
                self.dfs(neighbor, visited, stack)
                stack.append(neighbor)
        stack.append(node)

    def topological_sort(self):
        visited = [False] * len(self.parent)
        stack = []
        for node in range(len(self.parent)):
            if not visited[node]:
                self.dfs(node, visited, stack)
        return stack

# Example graph adjacency list
graph = {
    0: [1, 7],
    1: [0, 2, 3],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [],
    5: [],
    6: [],
    7: [0, 4]
}

dsu = DisjointSet(8)
for node in graph:
    dsu.parent[node] = node

for node1, node2 in graph.items():
    for node in node2:
        dsu.union(node1, node)

topological_sort = dsu.topological_sort()
print('Topological Sort:', topological_sort)

That's it for our DSU Applications lesson! We've covered the Minimum Spanning Tree and Depth-First Search (including Topological Sorting). With a solid understanding of DSU, you're well on your way to mastering advanced data structures and algorithms.

Keep learning and happy coding! 💻🙌