Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python Kruskal: minimum spanning forests and disconnected graphs

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

Kruskal selects undirected edges by increasing weight and joins only components that are still separate.

Download Python source kit

Operation contract

The network function returns the forest weight and remaining component count. Negative weights are permitted. Self-loops cannot join components and parallel edges compete normally. A disconnected input produces a forest rather than pretending to connect every site. Edges are sorted into a fresh sequence and the caller’s input order remains untouched.

Failure and ownership boundary

A minimum spanning forest does not answer directed shortest-path queries. The fixture validates integer endpoints and bounds nodes and edges before sorting. Tied weights may permit several equally cheap forests; this contract returns only weight and component count, avoiding an unnecessary promise about the selected edge identity. Python union-find: connected groups with path compression and Python Dijkstra: nonnegative weights and stale heap entries make that distinction concrete.

Working program

python
def network_forest(count, edges):
    if type(count) is not int or not 1 <= count <= 32 or len(edges) > 256:
        raise ValueError("network budget exceeded")
    for start, end, weight in edges:
        if any(type(value) is not int for value in (start, end, weight)):
            raise ValueError("integer edge required")
        if not 0 <= start < count or not 0 <= end < count or abs(weight) > 1000000:
            raise ValueError("invalid edge")
    parents = list(range(count))
    sizes = [1] * count
    def find(site):
        while parents[site] != site:
            parents[site] = parents[parents[site]]
            site = parents[site]
        return site
    total = 0
    components = count
    for start, end, weight in sorted(edges, key=lambda edge: edge[2]):
        first, second = find(start), find(end)
        if first == second:
            continue
        if sizes[first] < sizes[second]:
            first, second = second, first
        parents[second] = first
        sizes[first] += sizes[second]
        total += weight
        components -= 1
    return total, components

print(network_forest(4, [(0, 1, 4), (1, 2, 2), (0, 2, 3)]))
print(network_forest(2, [(0, 0, -5), (0, 1, -2)]))

Output

Output
(5, 2)
(-2, 1)

Costs and limits

Sorting E edges costs O(E log E). Size-weighted union with path compression gives near-constant amortized component operations, conventionally O(alpha(V)). Arrays use O(V) storage and sorting retains O(E) edge references.

Common Mistakes

  • A disconnected result is a forest, not a spanning tree.
  • Self-loops must not reduce the component count.

Connected lessons

Python union-find: connected groups with path compression, Python Dijkstra: nonnegative weights and stale heap entries, Python sorting: stable keys, independent output and explicit tie rules.

python
kruskal-forest
Storage details