Spanning Tree and Minimum Spanning Tree — Kruskal's and Prim's Algorithm

A Spanning Tree of a connected, undirected graph is a subgraph that includes all the vertices with the minimum number of edges needed to keep the graph connected, and without forming any cycles. A Minimum Spanning Tree (MST) is a spanning tree with the smallest possible total edge weight.

Kruskal's Algorithm

Kruskal's builds the MST by sorting all edges by weight and adding them one at a time, skipping any edge that would form a cycle (checked using a Union-Find/Disjoint Set structure), until all vertices are connected.

def kruskal(num_vertices, edges):
    parent = list(range(num_vertices))

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

    def union(x, y):
        parent[find(x)] = find(y)

    mst = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, w))
    return mst

Prim's Algorithm

Prim's builds the MST by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex already in the MST to a vertex outside it, typically using a priority queue.

import heapq

def prim(num_vertices, adj):
    visited = [False] * num_vertices
    min_heap = [(0, 0)]   # (weight, vertex)
    total_cost = 0

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total_cost += weight
        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v))
    return total_cost

Complexity

Applications

• Network design — laying cables or pipelines at minimum cost.
• Approximation algorithms for problems like the Traveling Salesman Problem.
• Cluster analysis in machine learning.