Kruskal's Algorithm for MST with DSU

1. What is a Minimum Spanning Tree (MST)?

First, let's define our goal. For any connected, undirected graph with weighted edges, a Minimum Spanning Tree (MST) is a subgraph that meets three conditions:

1. It connects all the vertices in the original graph.
2. It contains no cycles (making it a "tree").
3. The sum of the weights of all its edges is the minimum possible.

A key property to remember is that for a graph with V vertices, its MST will always have exactly V - 1 edges.

2. The Greedy Strategy of Kruskal's Algorithm

Kruskal's algorithm uses a simple and elegant greedy strategy. The core idea is to build the MST by always picking the "best" edge available at each step.

The algorithm proceeds as follows:

1. Sort Edges: Create a list of all edges in the graph and sort them in non-decreasing order of their weights.
2. Iterate and Build: Initialize an empty list for the MST. Iterate through the sorted edges one by one.
3. Check for Cycles: For each edge connecting vertices u and v, check if adding it to our tree would form a cycle.
4. Add or Discard:
   • If adding the edge does not create a cycle, add it to the MST.
   • If adding the edge does create a cycle, discard it and move to the next edge.
5. Stop: Continue until the MST has V - 1 edges.

The most critical part of this process is step 3: "check if adding it would form a cycle." How can we do this efficiently? This is where your DSU knowledge comes into play.

3. Using DSU for Cycle Detection

The DSU data structure is the perfect tool for cycle detection in Kruskal's algorithm. Here's how it works:

• We can think of each set in our DSU as a connected component of the forest we are building.
• Initially, each vertex is in its own set (its own component).
• When we consider an edge (u, v), we use the find operation to check which components u and v belong to.
  • If find(u) != find(v), the two vertices are in different components. Adding the edge (u, v) will connect these two components but won't create a cycle. So, we add the edge to our MST and perform union(u, v) to merge the two components.
  • If find(u) == find(v), the two vertices are already in the same component. This means there is already a path between them. Adding the edge (u, v) would create a cycle. Therefore, we must discard this edge.

Let's watch a video that visualizes this process.

4. The Python Implementation

Now, let's translate this logic into Python. The implementation requires two main parts: the DisjointSet class you are already familiar with, and the kruskal_mst function that orchestrates the algorithm.

Here is the complete code, adapted from the resource you just read, for your reference. It combines the DisjointSet class (which should be very familiar from our last lesson) and the main function.

# Part 1: The DSU class (with path compression and union by rank)
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            # Path compression
            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:
            # Union by rank
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True  # Return True to indicate a successful merge
        return False  # Return False if they were already in the same set

# Part 2: The Kruskal's MST function
def kruskal_mst(vertices, edges):
    # 'edges' is expected to be a list of tuples: (weight, u, v)
    
    # 1. Sort all edges in non-decreasing order of weight
    edges.sort()
    
    dsu = DisjointSet(vertices)
    mst = []
    
    # 2. Iterate through all sorted edges
    for weight, u, v in edges:
        # 3. If including this edge does not form a cycle, include it
        #    and unite the two sets. The union method handily checks this for us.
        if dsu.union(u, v):
            mst.append((u, v, weight))
    
    return mst

# --- Example Usage ---
V = 4
# Edges format: (weight, vertex1, vertex2)
edge_list = [
    (10, 0, 1),
    (6, 0, 2),
    (5, 0, 3),
    (15, 1, 3),
    (4, 2, 3)
]

minimum_spanning_tree = kruskal_mst(V, edge_list)

total_weight = 0
print("Edges in the Minimum Spanning Tree:")
for u, v, w in minimum_spanning_tree:
    print(f"Edge: {u}-{v}, Weight: {w}")
    total_weight += w

print(f"\nTotal weight of MST: {total_weight}")

5. Complexity Analysis

Understanding the performance of an algorithm is crucial in competitive programming.

The Space Complexity is O(V + E), required to store the DSU's parent/rank arrays (O(V)) and the list of edges (O(E)).

Conclusion

Congratulations on completing not just this lesson, but the entire course! You have journeyed from Python basics to advanced data structures and algorithms used by competitive programmers worldwide.

Key Takeaways from this Lesson:

• Kruskal's algorithm is a greedy algorithm that finds an MST by iteratively adding the cheapest edge that doesn't form a cycle.
• The Disjoint Set Union (DSU) data structure is the key to implementing Kruskal's efficiently, providing a near-constant time method for cycle detection.
• The overall time complexity is O(E log E), dominated by the initial sorting of edges.

What's Next?
Your journey in competitive programming is just beginning. The concepts you've learned—from complexity analysis and core data structures to advanced techniques like dynamic programming, backtracking, and graph algorithms—are your foundational toolkit.

To continue growing your skills, I strongly recommend:

• Consistent Practice: Solve problems regularly on platforms like LeetCode, CodeChef, and HackerRank. The resources from this lesson, like "Min Cost to Connect All Points", are great starting points for applying MSTs.
• Review and Reinforce: Revisit challenging topics. Sometimes a concept clicks only after seeing it applied in different problem contexts.
• Explore Further: This course covered the fundamentals. There are many more fascinating topics to explore, such as string algorithms (KMP, Z-algorithm), computational geometry, and more advanced DP or graph problems.

You have built a solid foundation. Keep coding, stay curious, and enjoy the challenge of solving complex problems. Well done