Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Finding a Minimum Spanning Tree with Kruskal’s Algorithm

A minimum spanning tree (MST) connects every vertex in a weighted, undirected graph while using the smallest possible total edge weight. It contains no cycles, and a graph with (V) vertices has exactly (V-1) edges in its spanning tree. This makes the structure useful for designing networks that reach every location without paying for unnecessary links.

Kruskal’s algorithm solves this problem by considering edges in ascending order of weight. It accepts an edge when that edge joins two currently separate components. If the edge would create a cycle, the algorithm skips it. A disjoint-set union structure, also called union-find, makes those connectivity checks efficient.

The method applies to many practical problems: laying fibre between buildings, connecting substations, planning roads, or designing a low-cost computer network. For example, a planner comparing links between suburbs in Sydney or Melbourne can treat locations as vertices and construction costs as edge weights.

Kruskal’s approach is also a useful lesson in greedy algorithms. Each decision looks local, yet the full set of accepted edges is globally optimal. Understanding why this works helps when studying related optimisation techniques, including the ideas behind the Hungarian algorithm, which solves a different type of weighted matching problem.

Graph Model And Spanning Tree Properties

Represent each possible connection as an edge ((u, v, w)), where (u) and (v) are vertices and (w) is its weight. The weight might represent distance, financial cost, installation time, energy use, or a combined score. Kruskal’s algorithm assumes that the graph is undirected because a connection between two locations works in both directions.

A spanning tree must satisfy three conditions. It includes every vertex, it contains no cycle, and every pair of vertices is connected by a path. The absence of cycles means that removing any one tree edge disconnects the graph. In a network design context, that can minimise cost, although a real system may add backup links later for resilience.

Suppose the available edges are:

Kruskal first chooses A–B, then B–C. A–C is rejected because A and C are already connected through B. The algorithm then chooses C–D, producing a spanning tree with total weight (1+2+4=7). The rejected edge would have formed a cycle.

If several edges have the same weight, more than one minimum spanning tree may exist. Their structures can differ, but their total weight is equal. This matters when a program needs a predictable result: sorting ties consistently can make output reproducible, even though it does not change optimality.

The Greedy Process And Union-Find

The core procedure begins by sorting all edges from the smallest weight to the largest. Initially, each vertex belongs to its own component. For every edge ((u,v)), the algorithm checks whether (u) and (v) have different representatives. If they do, the edge is safe to add, and the two components are merged.

A disjoint-set union data structure supports two operations. find(x) returns the representative of the component containing x, while union(x, y) combines two components. Path compression makes future find operations faster by attaching visited vertices directly to a root. Union by rank or union by size keeps the component trees shallow.

The pseudocode is short:

sort edges by increasing weight
make a separate set for every vertex
tree = empty set

for each edge (u, v, weight):
    if find(u) != find(v):
        add edge to tree
        union(u, v)

    if tree contains V - 1 edges:
        stop

return tree

The cycle test is the key decision. If both endpoints have the same representative, a path already connects them, so adding the edge would create a cycle. If their representatives differ, joining them cannot create a cycle because the two components were previously separate.

The greedy choice is justified by the cut property. For any division of the vertices into two groups, the lightest edge crossing that division can safely belong to some MST. At each stage, Kruskal selects the lightest available edge that joins separate components, so it repeatedly makes a safe choice. The resulting tree therefore has minimum total weight.

Python Implementation And Complexity

A practical Python implementation can use dictionaries for arbitrary vertex labels such as suburb names, station codes, or integers. The parent dictionary records each vertex’s representative, while the size dictionary supports balanced merging.

def kruskal(vertices, edges):
    parent = {vertex: vertex for vertex in vertices}
    size = {vertex: 1 for vertex in vertices}

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

    def union(a, b):
        root_a = find(a)
        root_b = find(b)

        if root_a == root_b:
            return False

        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a

        parent[root_b] = root_a
        size[root_a] += size[root_b]
        return True

    tree = []
    total_weight = 0

    for weight, a, b in sorted(edges):
        if union(a, b):
            tree.append((a, b, weight))
            total_weight += weight

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

    if len(tree) != len(vertices) - 1:
        raise ValueError("The graph is disconnected")

    return tree, total_weight

Here, each edge is stored as (weight, a, b), so Python’s default sorting orders the edges by weight first. The function raises an error when no spanning tree exists. If the input graph has several disconnected parts, Kruskal naturally produces a minimum spanning forest, but it cannot connect components for which no edge is available.

Sorting dominates the running time. With (E) edges, sorting costs (O(E\log E)). The union-find operations are almost constant on average, with amortised complexity (O(\alpha(V))), where (\alpha) is the very slowly growing inverse Ackermann function. The total complexity is therefore (O(E\log E)), and the edge list requires (O(E)) storage.

A useful debugging technique is to inspect the accepted edges after every successful union. The result should contain at most (V-1) edges, never contain a cycle, and connect all vertices when the input is connected. If labels come from user data, validate them before building the parent map; a missing or inconsistent label can look like an algorithm error when it is actually an input problem. Technical questions and corrections can also be directed through the site’s contact page.

Comparing Kruskal With Prim’s Algorithm

Kruskal and Prim both find minimum spanning trees, but they grow the solution differently. Kruskal starts with individual components and joins them globally by selecting the lightest remaining edge. Prim starts from one chosen vertex and repeatedly adds the cheapest edge leaving the current tree.

Kruskal is often convenient when the graph is already represented as an edge list. This is common in programming problems and in datasets containing pairs of locations with costs. Prim can be attractive for dense graphs stored as adjacency matrices or adjacency lists, particularly when a priority queue gives efficient access to nearby candidate edges.

For a sparse graph, both algorithms can perform well with suitable data structures. Kruskal’s sorting step is easy to reason about and its union-find implementation is reusable. Prim’s algorithm may avoid sorting every edge, but it needs a priority queue and careful handling of stale entries. The best choice depends on the input representation rather than on a universal rule that one algorithm is always faster.

Neither algorithm handles negative weights as a special problem. A negative edge can still be processed first, and the minimum spanning tree remains well-defined as long as the graph is undirected. Self-loops should be ignored because they can never help connect two components. Parallel edges are valid; the lighter one will generally be considered first.

The output also has a different meaning from a shortest-path tree. A shortest-path algorithm minimises travel cost from one source to destinations, while an MST minimises the sum of selected links across the whole network. A tree that is cheapest to build may give a particular pair of vertices a longer route than another available network would.

Practical Uses And Common Pitfalls

Network planners can use an MST as a baseline for connecting Australian suburbs, farms, campuses, or remote facilities. A telecommunications company extending fibre near Brisbane might model trenching costs between exchanges and choose a low-cost backbone. A transport analyst could compare links between stations in Melbourne, while recognising that passenger capacity, safety and backup routes require constraints beyond a basic MST.

The model can also reflect local operating realities. Australian households often rely on broadband, mobile services and electricity connections every day, so an outage-prone tree may be unacceptable even when it is cheap. Public transport systems such as Sydney’s Opal network or Melbourne’s Myki-connected services need redundancy and service-frequency analysis; an MST can help estimate a minimum physical connection plan, but it does not replace timetable or reliability modelling.

Weights should be defined carefully. Straight-line distance may be misleading when a route crosses a river, protected land or a steep section of terrain. A construction estimate could include labour, materials, traffic management and environmental approvals. In Australia, projects may also need to account for bushfire exposure, flooding in Queensland, or long distances between regional communities. The cheapest mathematical edge is not automatically the cheapest buildable route.

Privacy and governance matter when vertices or weights come from operational data. A network project using customer addresses should follow the Australian Privacy Act 1988 and apply data minimisation, access controls and suitable de-identification. In a commercial setting, cost figures may be sensitive, while public infrastructure decisions may need transparent assumptions and audit trails.

An MST is also a starting point rather than a complete engineering design. If every connection must survive a single failure, a tree is insufficient because removing one edge can split it. Designers may first compute the MST to understand the lower bound on connection cost, then add redundant edges, capacity limits, geographic restrictions or reliability requirements. For optimisation models involving resource constraints, the simplex algorithm addresses a different problem and may be used alongside graph methods rather than instead of them.