Minimum Spanning Trees

A minimum spanning tree is a subset of the edges of a connected, weighted, undirected graph that connects every node, contains no cycles, and has the smallest possible total weight. The classic use is laying out a network: cable, roads, or pipes, where every node must be connected and you want the cheapest way to do it without paying for redundant loops.

Two facts shape the solution. First, a tree on n nodes has exactly n minus one edges, so the answer always has that many edges. Second, the problem has a cut property: for any cut of the graph, the cheapest edge crossing that cut is safe to include in some minimum spanning tree. That property is what makes the greedy algorithms correct.

The trade-off to name is that a minimum spanning tree minimises the total weight, not the longest path or the worst edge. A network that is cheap in total can still contain a very long path, and if you care about latency rather than cost, you need a different objective. The other point is that the graph must be undirected and connected for the standard definition to apply, and the weights must be comparable, which they are for costs but not for something like a trade off between price and latency.

Sort the edges by weight, then add them one at a time, skipping any edge that would create a cycle. A union find structure tells you in near constant time whether two nodes are already connected.

def minimum_spanning_tree(edges):
    parent = {}

    def find(node):
        parent.setdefault(node, node)
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node

    total = 0
    chosen = []
    for weight, u, v in sorted(edges):
        root_u = find(u)
        root_v = find(v)
        if root_u != root_v:
            parent[root_v] = root_u
            total += weight
            chosen.append((u, v, weight))
    return total, chosen


edges = [(1, "A", "B"), (2, "B", "C"), (3, "A", "C"), (4, "C", "D")]
total, chosen = minimum_spanning_tree(edges)
print(total)
print(chosen)

The outputs are 7 and the list of the edges A to B with weight 1, B to C with weight 2, and C to D with weight 4. The edge A to C with weight 3 was skipped because A and C are already connected through B.

The mechanism is the cut property applied greedily. When you consider edges in increasing weight order, the next edge you accept is the cheapest one that does not create a cycle, and the cheapest edge crossing any cut is always safe to include in some minimum spanning tree.

The trade-off to name is the sorting cost. Kruskal sorts all the edges, which is O of E log E, and then each union find operation is nearly constant, so the total is O of E log E. Prim's algorithm in the next answer does not need to sort the whole edge list and is often faster on dense graphs, whereas Kruskal is usually better on sparse ones. The other detail is that the union find here uses a dictionary so the structure only knows about nodes that appear in the edges, which is convenient when the graph is given as an edge list.

Grow the tree one node at a time. Start from any node, keep a heap of the edges that cross from the tree to the rest of the graph, and each time take the cheapest edge that reaches a new node.

import heapq


def minimum_spanning_tree_prim(graph):
    visited = set()
    heap = []
    start = next(iter(graph))
    heapq.heappush(heap, (0, start))
    total = 0
    edges = []
    while heap:
        weight, node = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        total += weight
        if node != start:
            edges.append(weight)
        for neighbour, cost in graph[node]:
            if neighbour not in visited:
                heapq.heappush(heap, (cost, neighbour))
    return total, edges


graph = {"A": [("B", 1), ("C", 3)],
         "B": [("A", 1), ("C", 2)],
         "C": [("A", 3), ("B", 2), ("D", 4)],
         "D": [("C", 4)]}
total, edges = minimum_spanning_tree_prim(graph)
print(total)
print(sorted(edges))

The outputs are 7 and the list 1, 2, 4. The tree takes the cheap edge to B, the cheaper edge to C, and then the only edge to D.

The mechanism is again the cut property. At every moment the tree and the rest of the graph form a cut, and the heap holds the cheapest edge crossing it. Taking the minimum from the heap therefore picks a safe edge every time, which is why the greedy choice is correct.

The trade-off to name is that Prim needs an adjacency list and a priority queue, so it runs in O of E log V and does not need to sort the whole edge list. That makes it faster than Kruskal on dense graphs, where the sort dominates, while Kruskal is simpler and often faster on sparse ones. The extra cost of Prim is that the heap can hold many stale entries for nodes that were already visited, so you have to skip them on the way out, and the memory used by the heap is proportional to the number of edges crossing the cut rather than to the size of the tree.