Kruskal’s Algorithm in Python: Minimum Spanning Trees with Union-Find

Quick answer: Kruskal’s algorithm sorts weighted undirected edges and accepts the next edge only when it connects different components. A disjoint-set union-find structure makes cycle checks efficient and yields a minimum spanning tree or forest.

Kruskal’s algorithm finds a minimum spanning tree (MST) for an undirected weighted graph. The MST connects every vertex with the lowest possible total edge weight, without creating cycles.

The algorithm is greedy: it sorts all edges by weight, then keeps taking the cheapest edge that connects two different components. A union-find data structure makes the cycle check fast.

When to Use Kruskal’s Algorithm

Use Kruskal’s algorithm when you have a graph represented as an edge list, such as (source, destination, weight) tuples. It is a good fit for network design, road or cable planning examples, clustering problems, and interview questions about minimum spanning trees.

The graph should be undirected. If the graph is connected, Kruskal’s algorithm returns one minimum spanning tree. If the graph is disconnected, the same idea produces a minimum spanning forest, but there is no single MST that reaches every vertex.

Kruskal’s Algorithm Steps

1. List all vertices and weighted edges.
2. Sort the edges from the smallest weight to the largest weight.
3. Start with an empty MST.
4. Read each sorted edge. Add it only if it does not create a cycle.
5. Stop when the MST has V - 1 edges, where V is the number of vertices.

The important part is step 4. Union-find keeps track of which vertices already belong to the same connected component. If both endpoints of an edge are already in the same component, adding that edge would create a cycle, so the edge is skipped.

Python Implementation

This implementation uses path compression and union by rank. It also raises a clear error when the graph is disconnected or when an edge mentions an unknown vertex.

def kruskal(vertices, edges):
    if not vertices:
        return [], 0

    parent = {vertex: vertex for vertex in vertices}
    rank = {vertex: 0 for vertex in vertices}

    def find(vertex):
        if parent[vertex] != vertex:
            parent[vertex] = find(parent[vertex])
        return parent[vertex]

    def union(left, right):
        root_left = find(left)
        root_right = find(right)

        if root_left == root_right:
            return False

        if rank[root_left] < rank[root_right]:
            parent[root_left] = root_right
        elif rank[root_left] > rank[root_right]:
            parent[root_right] = root_left
        else:
            parent[root_right] = root_left
            rank[root_left] += 1

        return True

    mst = []
    total_weight = 0

    for u, v, weight in sorted(edges, key=lambda edge: edge[2]):
        if u not in parent or v not in parent:
            raise ValueError(f"Unknown vertex in edge: {(u, v, weight)}")

        if union(u, v):
            mst.append((u, v, weight))
            total_weight += weight

        if len(mst) == len(vertices) - 1:
            break

    if len(mst) != len(vertices) - 1:
        raise ValueError("Graph is disconnected; no single MST exists")

    return mst, total_weight

Example Graph

The graph below has six vertices and nine weighted edges. The function returns the chosen MST edges and their total weight.

vertices = {"A", "B", "C", "D", "E", "F"}

edges = [
    ("A", "B", 4),
    ("A", "C", 1),
    ("B", "C", 2),
    ("B", "D", 5),
    ("C", "D", 8),
    ("C", "E", 10),
    ("D", "E", 2),
    ("D", "F", 6),
    ("E", "F", 3),
]

mst, total = kruskal(vertices, edges)
print(mst)
print(total)

Output

[('A', 'C', 1), ('B', 'C', 2), ('D', 'E', 2), ('E', 'F', 3), ('B', 'D', 5)]
13

The algorithm first picks the low-weight edges A-C, B-C, D-E, and E-F. It skips edges that would make a cycle, then adds B-D to connect the two remaining components. The result has 6 - 1 = 5 edges and total weight 13.

Time and Space Complexity

The dominant cost is sorting the edges, so the time complexity is O(E log E), where E is the number of edges. The union-find operations are very close to constant time in practice because path compression and union by rank keep the trees shallow.

The space complexity is O(V) for the parent and rank dictionaries, plus the space used to store the result MST.

Disconnected Graphs

A disconnected graph cannot have one spanning tree because at least one vertex cannot be reached from the others. The implementation above raises ValueError in that case:

kruskal({"A", "B", "C"}, [("A", "B", 1)])
# ValueError: Graph is disconnected; no single MST exists

If your use case needs a minimum spanning forest instead, remove the final connectivity check and return the edges collected for each component.

Common Mistakes

• Using a directed graph. Kruskal’s algorithm is for undirected weighted graphs.
• Skipping cycle detection. Sorting edges is not enough; you must reject edges that connect vertices already in the same component.
• Forgetting disconnected inputs. A disconnected graph can produce a forest, but not a single MST.
• Sorting by the wrong tuple item. In this example, the weight is at index 2, so the key is lambda edge: edge[2].

Kruskal vs Prim

Kruskal’s algorithm sorts edges and grows the MST by joining components. Prim’s algorithm starts from one vertex and grows outward by choosing the cheapest edge leaving the current tree. Kruskal is often simpler when your input is already an edge list. Prim is often convenient when you work with adjacency lists and priority queues.

Related Python Guides

If you want to compare this with another sorting-based algorithm, read Insertion Sort in Python. If your graph data is stored as nested lists, the Python 2D list guide explains the list patterns used in many beginner graph examples.

Official References

• Python Sorting HOWTO
• NetworkX minimum_spanning_tree documentation

Conclusion

Kruskal’s algorithm in Python is mostly about combining two ideas: sort the edges by weight, then use union-find to reject cycles. With path compression and union by rank, the code stays compact while still handling realistic MST inputs efficiently.

Sort The Edges

Order edges by weight, then process them from lightest to heaviest. Define deterministic tie behavior when reproducible output matters.

Use Union-Find

Find identifies a component representative and union merges two components. Path compression and union by rank or size keep repeated checks efficient.

Reject Cycles

An edge whose endpoints already have the same representative would create a cycle, so skip it. Accept an edge only when the representatives differ.

Stop At The Tree Size

A connected graph’s spanning tree has V – 1 edges. Stop once that many edges are accepted, or continue to build a forest when the graph is disconnected.

Handle Disconnected Inputs

If fewer than V – 1 edges are accepted, return a minimum spanning forest or a documented disconnected-graph result rather than claiming a single tree.

Test Weights And Components

Test empty and single-vertex graphs, ties, negative weights if allowed, parallel edges, disconnected components, cycles, union-find paths, and total weight against a small reference.

Use the Kruskal algorithm reference for the greedy context. Related Python Pool references include tests and edge lists.

For related graph algorithms, compare graph tests, edge lists, and component mappings before implementing union-find.

Frequently Asked Questions

What does Kruskal’s algorithm find?

It finds a minimum spanning tree of a weighted undirected graph, or a minimum spanning forest when the graph is disconnected.

Why does Kruskal’s algorithm sort edges?

Processing edges from lowest weight upward makes each accepted edge a safe choice under the spanning-tree greedy property.

What is union-find used for?

A disjoint-set structure tracks connected components and quickly tells whether adding an edge would create a cycle.

What is the complexity of Kruskal’s algorithm?

Sorting edges usually dominates at O(E log E); near-constant amortized union-find operations add efficient component checks.