Kruskal's Algorithm

A Minimum Spanning Tree (MST) is a fundamental concept in graph theory. In a connected graph with weighted edges, an MST is a specific subset of those edges that connects every single vertex together without creating any closed loops (cycles), while ensuring the total combined weight of all the edges is as small as possible.

The Forest Builder Principle

Instead of growing a single tree from a starting point, Kruskal's treats every node as its own isolated tree (a forest). Here is the step-by-step logic:

• Extract all the edges from the graph and sort them from lightest (cheapest) to heaviest.
• Look at the cheapest edge available.
• Use the Union-Find structure to check if the two nodes connected by this edge are already part of the same network.
• If they belong to different networks, add the edge (Union) to merge them.
• If they are already in the same network, adding this edge would create a cycle. Discard it and move to the next one.
• Stop when all nodes are merged into a single, fully connected tree.

Algorithm Walkthrough

Below is the Python implementation used in our animation engine. Notice the helper functions find() and union() which form the backbone of the cycle detection.

def kruskal():
    # 1. Extract and sort all unique edges from the graph
    edges_list = []
    for u, dict_voisins in GRAPH_EDGES.items():
        for v, w in dict_voisins.items():
            # Avoid adding duplicate edges (u,v) and (v,u)
            if (v, u, w) not in edges_list: 
                edges_list.append((u, v, w))
                
    # Sort by ascending weight
    edges_list.sort(key=lambda x: x[2])
    
    # 2. Union-Find structure to detect cycles
    parent = {n: n for n in GRAPH_EDGES.keys()}
    
    def find(i):
        if parent[i] == i: return i
        parent[i] = find(parent[i]) # Path compression
        return parent[i]
        
    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j
            return True
        return False

    mst_weight = 0
    
    # 3. Selection animation
    for u, v, w in edges_list:
        select(u)
        color_edge(u, v, "#FBBF24") # Visual: Yellow (Evaluating)
        
        if union(u, v):
            color_edge(u, v, "#34D399") # Visual: Green (Accepted!)
            mst_weight += w
            visit(v, f"Edge {u}-{v} accepted (weight {w})")
        else:
            color_edge(u, v, "#EF4444") # Visual: Red (Rejected, creates a cycle)
            
    print(f"Total weight of the Minimum Spanning Tree (Kruskal): {mst_weight}")

kruskal()

Complexity

The performance of Kruskal's algorithm is heavily bottlenecked by how fast we can sort the edges.