Kruskal's Minimum Spanning Tree Algorithm

How Kruskal's Algorithm Works

Kruskal's algorithm finds a minimum spanning tree for a connected weighted graph. It adds the smallest edge that doesn't create a cycle, continuing until all nodes are connected. The algorithm uses a disjoint-set data structure to efficiently check for cycles.

Color representation:

• Gray edges are not part of the MST
• Yellow edge is the current edge being considered
• Green edges are part of the MST

function kruskal(graph):
    edgeList = getAllEdgesSortedByWeight(graph)
    disjointSet = DisjointSet(graph.vertices)
    mst = []

    for each edge in edgeList:
        if disjointSet.find(edge.source) != disjointSet.find(edge.destination):
            disjointSet.union(edge.source, edge.destination)
            mst.append(edge)
            visualize(mst, edge)
        
        if mst.length == graph.vertices - 1:
            break

    return mst

function visualize(mst, currentEdge):
    // Update UI to show:
    // 1. All edges considered so far
    // 2. Edges included in the MST
    // 3. Highlight the current edge being considered
    // 4. Show the forest of trees as they're being connected