Kruskal's algorithm: connect vertices at the lowest total cost

The direct A–C link is cheaper than the link to D, but buying it would not reach a new vertex. This is the part that “pick the cheapest edges” leaves out: the chosen edges must connect the graph without paying for a loop.

Join two separate groups with a cheap edge#

In this illustrative, undirected graph, the available edges and costs are A–B:1, B–C:2, A–C:3, C–D:4 and B–D:5. Consider them in cost order:

Edge	Decision	Connected groups afterwards
A–B, cost 1	Keep it.	A,B; C; D
B–C, cost 2	Keep it.	A,B,C; D
A–C, cost 3	Skip it: A and C are already connected.	A,B,C; D
C–D, cost 4	Keep it.	A,B,C,D
B–D, cost 5	Skip it: B and D are already connected.	A,B,C,D

The kept edges cost 1 + 2 + 4 = 7. They connect all four vertices with no cycle. Such a structure is a spanning tree; a cheapest one is a minimum spanning tree.

Why is a cheapest eligible edge safe? Take one currently connected group and look at edges that leave it. A cheapest crossing edge can be included in a minimum spanning tree. If a minimum tree omits that edge, adding it creates a cycle. That cycle has another edge crossing out of the group, with no lower weight. Remove that other crossing edge: the result is still a tree and costs no more. Kruskal repeats this choice as groups join.

Try the worked example

Next edge

Remember which vertices are already connected#

The code needs to answer “are these two endpoints already connected?” without walking every existing route each time. Union-find, also called disjoint-set union, maintains separate groups. find(x) returns the representative of x’s group. Joining two representatives combines their groups.

This Python example takes a list of distinct vertex names and a list of edge tuples (weight, start, end). Each edge is treated as undirected. Sorting uses only the weight, so equal weights do not require comparing the vertex labels.

def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    rank = {v: 0 for v in vertices}
    if any(u not in parent or v not in parent for _, u, v in edges):
        raise ValueError("every edge endpoint must be a listed vertex")

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

    chosen = []
    for weight, u, v in sorted(edges, key=lambda edge: edge[0]):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        if rank[ru] < rank[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        if rank[ru] == rank[rv]:
            rank[ru] += 1
        chosen.append((weight, u, v))
    return chosen

find shortens future lookups by updating a visited vertex to point to the group’s representative. The rank values guide which root becomes the parent when two groups join. Those are efficiency measures; the central correctness check is that an accepted edge joins different groups.

The union-find parent links are bookkeeping, not necessarily edges in the chosen tree. Read the returned chosen list to find the actual selected graph edges.

What changes with ties or disconnected vertices?#

Equal weights can lead to several different minimum trees. The example retains the input order among equal-weight edges; that selects one valid result, not the uniquely correct result.

If no edge connects two parts of the input, no algorithm can invent that connection. The function then builds one minimum tree per connected component: a minimum spanning forest. An isolated vertex is a component with no selected edges, so it does not appear in the edge list returned by this function.

For E edges, sorting takes O(E log E) time. Initialising the groups takes O(V) for V vertices; with the shown union-find optimisations, the grouping operations add a much smaller amortised cost per edge. The sorted copy uses O(E) extra space and the grouping structures use O(V).

Negative weights are allowed. Bellman–Ford also accepts negative edges, but answers a different question about cheapest routes from a start and reachable negative cycles. Dijkstra’s algorithm finds shortest routes for nonnegative weights. A minimum spanning tree minimises the cost of the whole connecting structure, not each individual journey through it.

Questions people also ask

2 QUESTIONS

▸ Can edge weights be negative?

Yes. Kruskal compares edge weights to minimise a tree’s total weight. A negative edge does not invalidate that procedure; this is different from Dijkstra’s nonnegative-weight requirement.

▸ Does a minimum spanning tree give shortest routes?

Not generally. It minimises the total weight of the selected tree. The route between two particular vertices through that tree can be more expensive than a route using an omitted edge.