Spanning Tree & Minimum Spanning Tree

A spanning tree of an undirected graph is a subgraph that includes all vertices but only enough edges to keep the graph connected (exactly |V| - 1 edges). When edges have weights, the Minimum Spanning Tree (MST) is the spanning tree with the smallest total edge weight.

Properties of an MST

• Contains exactly V - 1 edges for V vertices.
• No cycles — it is a tree by definition.
• The total weight is minimal among all possible spanning trees.
• If all edge weights are distinct, the MST is unique.

Prim's Algorithm (Greedy, Vertex-Based)

Prim's algorithm grows the MST one vertex at a time. It starts from an arbitrary vertex and repeatedly adds the cheapest edge that connects a visited vertex to an unvisited one.

How it works

1. Pick any starting vertex. Mark it as visited.
2. Consider all edges from visited vertices to unvisited vertices.
3. Pick the edge with the smallest weight. Add it to the MST.
4. Mark the newly connected vertex as visited.
5. Repeat steps 2—4 until all vertices are visited.

def prim(graph, start):
    n = len(graph)
    visited = [False] * n
    min_edge = [float('inf')] * n
    min_edge[start] = 0
    total_weight = 0

    for _ in range(n):
        u = -1
        # Pick the unvisited vertex with smallest edge
        for v in range(n):
            if not visited[v] and (u == -1 or min_edge[v] < min_edge[u]):
                u = v
        visited[u] = True
        total_weight += min_edge[u]
        # Update edges to neighbors
        for v, w in enumerate(graph[u]):
            if w and not visited[v] and w < min_edge[v]:
                min_edge[v] = w
    return total_weight

Time complexity: O(V²) with an adjacency matrix, or O(E log V) with a binary heap.

Kruskal's Algorithm (Edge-Based, Union-Find DSU)

Kruskal's algorithm sorts all edges by weight, then adds them one by one — skipping any edge that would create a cycle. It uses a Disjoint Set Union (DSU) or Union-Find data structure to detect cycles efficiently.

How it works

1. Sort all edges by weight in ascending order.
2. Initialize a DSU where each vertex is its own parent.
3. For each edge (u, v) in sorted order:
   • If find(u) != find(v), add the edge to the MST and union the sets of u and v.
4. Stop when the MST has V - 1 edges.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

def kruskal(vertices, edges):
    edges.sort(key=lambda e: e[2])
    dsu = DSU(vertices)
    mst_weight = 0
    count = 0
    for u, v, w in edges:
        if dsu.union(u, v):
            mst_weight += w
            count += 1
            if count == vertices - 1:
                break
    return mst_weight

Time complexity: O(E log E) due to sorting, or O(E log V) with efficient DSU operations.

Comparison: Prim vs Kruskal

Applications of MST

• Network design — laying fiber-optic cables, electrical grids, pipelines.
• Approximation algorithms — the MST is used as a building block for approximate solutions to NP-hard problems like the Traveling Salesman Problem.
• Clustering — single-linkage clustering is essentially Kruskal's algorithm stopped early.
• Image segmentation — graph-based segmentation uses MST concepts.
• Broadcast routing — MST minimizes total cost of broadcasting in a network.

edges = [
    (0, 1, 10), (0, 2, 6), (0, 3, 5),
    (1, 3, 15), (2, 3, 4), (3, 4, 8)
]