DSA Minimum Spanning Tree

A minimum spanning tree, or MST, connects every node of a weighted graph using the smallest possible total edge weight. The tree contains no loops, and every node stays reachable from every other node. A graph with V nodes always produces an MST with exactly V - 1 edges.

Imagine a company laying internet cables between five villages. Each possible cable has a cost based on distance. The goal is to link all villages while spending as little as possible. Extra cables that form loops only waste money, and an MST gives the cheapest layout.

Sample Graph

        4
   A ------- B
   |       / |
 2 |   1  /  | 5
   |    /    |
   C ------- D
        8

Edges: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8

The cheapest set of edges that connects all four nodes is B-C (1), A-C (2), and B-D (5). The total cost is 8.

Kruskal's Algorithm

Kruskal's algorithm sorts all edges from cheapest to costliest. The algorithm takes each edge in order and keeps it only when it joins two separate groups. Edges that would form a loop get skipped. A Union Find structure checks quickly whether two nodes already share a group.

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

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

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

edges = [(4, "A", "B"), (2, "A", "C"), (1, "B", "C"),
         (5, "B", "D"), (8, "C", "D")]
print(kruskal(["A", "B", "C", "D"], edges))
# (8, [('B', 'C', 1), ('A', 'C', 2), ('B', 'D', 5)])

Sorted edges: B-C 1, A-C 2, A-B 4, B-D 5, C-D 8

B-C 1  -> joins two groups, keep
A-C 2  -> joins two groups, keep
A-B 4  -> A and B already connected, skip (loop)
B-D 5  -> joins D to the group, keep
C-D 8  -> D already connected, skip (loop)

Total = 1 + 2 + 5 = 8

Prim's Algorithm

Prim's algorithm grows a single tree from a starting node. At each step the algorithm adds the cheapest edge that connects the tree to a new node. A priority queue serves up the cheapest edge quickly.

import heapq

def prim(graph, start):
    visited = set()
    heap = [(0, start)]
    total = 0
    while heap:
        cost, node = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        total += cost
        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                heapq.heappush(heap, (weight, neighbor))
    return total

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 1), ("D", 5)],
    "C": [("A", 2), ("B", 1), ("D", 8)],
    "D": [("B", 5), ("C", 8)]
}
print(prim(graph, "A"))   # 8

Start at A (tree = A)
cheapest edge out: A-C 2   -> tree = A, C
cheapest edge out: C-B 1   -> tree = A, C, B
cheapest edge out: B-D 5   -> tree = A, C, B, D

Total = 8

Kruskal vs Prim

• Kruskal works on the sorted list of edges and suits sparse graphs with few edges.
• Prim grows from a node and suits dense graphs with many edges.
• Both algorithms return a tree with the same minimum total cost.

Greedy Choice Behind Both Methods

Both algorithms pick the cheapest safe edge at every step and never regret the choice. The cut property backs this idea. Take any split of the nodes into two groups. The cheapest edge crossing the split always belongs to some MST. That guarantee makes the greedy method correct here.

Is the MST Unique

Two edges with the same weight can create several valid trees with the same total cost. The total stays fixed, though the exact edges may differ. When all edge weights are different, only one MST exists.

Real-Life Uses

Utility companies plan water pipes, power lines, and fiber cables. Road planners connect towns with the least paving. Network designers link office buildings at low cost. Clustering tools in data analysis group similar items by building an MST over distances.

Common Mistakes

Running the algorithms on a disconnected graph returns a forest, which means several trees instead of one. Check that the final edge count equals V - 1. Confusing an MST with a shortest path tree is another trap. An MST minimizes total cost across the whole tree, while a shortest path tree minimizes the cost from one start node to each destination.

Complexity Summary

• Kruskal: O(E log E), dominated by sorting the edges.
• Prim with a heap: O(E log V).
• Space: O(V + E).

Key Points

• An MST connects all nodes with the lowest total edge weight.
• The tree has V - 1 edges and no loops.
• Kruskal sorts edges and uses Union Find to skip loops.
• Prim grows one tree using a priority queue.
• Both algorithms use a greedy rule.