---

title: "Prim Algorithm & MST" description: "Implement Prim algorithm, expanding the minimum spanning tree gradually from a starting point." order: 2

Prim Algorithm

Prim is another MST method. Starting from one node, it repeatedly adds the nearest unconnected node.

Implementation

import math, heapq, random, matplotlib.pyplot as plt

def prim(points):
    n = len(points)
    visited = [False] * n
    pq = [(0, 0, -1)]
    mst = []
    total = 0
    while pq:
        cost, node, parent = heapq.heappop(pq)
        if visited[node]: continue
        visited[node] = True
        total += cost
        if parent != -1:
            mst.append((parent, node, cost))
        for neighbor in range(n):
            if not visited[neighbor]:
                dx = points[node][0] - points[neighbor][0]
                dy = points[node][1] - points[neighbor][1]
                dist = math.sqrt(dx*dx + dy*dy)
                heapq.heappush(pq, (dist, neighbor, node))
    return mst, total

random.seed(42)
pts = [(random.random()*100, random.random()*100) for _ in range(20)]
mst, total = prim(pts)
print(f"MST total length: {total:.2f}")

Correctness: Cut Property

For any cut splitting nodes into two groups, the minimum-weight crossing edge belongs to some MST.

Prim adds exactly the minimum crossing edge between visited and unvisited sets.

Three Implementations

| Implementation | Time | Best For | |---------------|:----:|----------| | Adjacency Matrix + Array | O(n^2) | Dense graphs | | Adjacency List + Binary Heap | O(m log n) | General | | Adj. List + Fibonacci Heap | O(m + n log n) | Theoretical |

Applications

• Network Design: Minimum cost cabling
• Cluster Analysis: Remove longest MST edge for clustering
• Image Segmentation: MST-based pixel clustering
• TSP Approximation: 2-approximation via MST

---

Kruskal vs Prim Decision Guide

| Comparison | Kruskal | Prim | |------------|:-------:|:----:| | Strategy | Sort edges, pick smallest | Expand from seed | | Structure | Union-Find | Priority Queue | | Time | O(E log E) | O(E log V) | | Best for | Sparse graphs (few edges) | Dense graphs (many edges) | | Difficulty | Medium (Union-Find) | Medium (Heap) |

Prim Core Idea

Each Prim step: from connected set, find shortest path to unconnected node. Classic greedy where local optimum = global optimum.

Next Chapter: Huffman Coding

MST shows greedy in network construction. Next chapter shows greedy in data compression.

Prim's Algorithm: Complete Implementation

import heapq

def prim_mst(graph, start=0):
    """
    Prim's algorithm for Minimum Spanning Tree.
    
    Args:
        graph: adjacency list graph[u] = [(v, weight), ...]
        start: starting vertex
    
    Returns:
        (mst_weight, mst_edges): total weight and list of edges in MST
    """
    n = len(graph)
    visited = [False] * n
    pq = [(0, start, -1)]  # (weight, vertex, parent)
    mst_weight = 0
    mst_edges = []

    while pq:
        weight, u, parent = heapq.heappop(pq)

        if visited[u]:
            continue

        visited[u] = True
        mst_weight += weight

        if parent != -1:
            mst_edges.append((parent, u, weight))

        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (w, v, u))

    return mst_weight, mst_edges


# Example graph: 5 vertices
graph = [
    [(1, 2), (3, 6)],           # vertex 0
    [(0, 2), (2, 3), (3, 8), (4, 5)],  # vertex 1
    [(1, 3), (4, 7)],           # vertex 2
    [(0, 6), (1, 8)],           # vertex 3
    [(1, 5), (2, 7)],           # vertex 4
]

weight, edges = prim_mst(graph)
print(f"MST Weight: {weight}")
print(f"MST Edges: {edges}")

Prim vs. Kruskal

| Aspect | Prim | Kruskal | |--------|------|--------| | Approach | Grow from a starting vertex | Pick smallest edges globally | | Data Structure | Priority queue (heap) | Union-Find (DSU) | | Best for | Dense graphs | Sparse graphs | | Time Complexity | O(E log V) with heap | O(E log E) with sorting | | Space Complexity | O(V) visited array | O(V) parent array | | Implementation | Slightly simpler | Slightly more complex |

Greedy Choice Property

In both Prim and Kruskal, the algorithm makes a locally optimal choice at each step:

• Prim: Always pick the cheapest edge connecting a visited vertex to an unvisited vertex
• Kruskal: Always pick the cheapest edge that does not create a cycle

Both lead to a globally optimal MST. This is the defining characteristic of greedy algorithms.

Applications

| Application | Description | |------------|-------------| | Network Design | Minimize cable length for connecting computers | | Circuit Design | Minimize wire length on a circuit board | | Transportation | Build roads connecting cities with minimum cost | | Clustering | MST-based clustering for data analysis | | Image Segmentation | Split images into regions using MST | | Approximation Algorithms | TSP approximation via MST doubling |

Time Complexity Analysis

| Implementation | Time | Space | |---------------|------|-------| | Naive (scan all vertices) | O(V²) | O(V) | | Binary Heap | O(E log V) | O(V + E) | | Fibonacci Heap | O(E + V log V) | O(V + E) |

For dense graphs (E ≈ V²), the naive O(V²) implementation can be faster than heap-based O(E log V).

Summary

Prim's algorithm finds the Minimum Spanning Tree by greedily expanding from a starting vertex. It always picks the cheapest edge connecting visited to unvisited vertices. The greedy choice leads to a globally optimal MST. Use Prim for dense graphs and Kruskal for sparse graphs.

Key takeaways:

• Prim = grow MST from a starting vertex
• Always pick the cheapest edge to an unvisited vertex
• Greedy choice → globally optimal solution
• Use priority queue (heap) for O(E log V)
• Use naive O(V²) for dense graphs
• Applications: network design, clustering, circuit design
• Prim vs Kruskal: Prim for dense, Kruskal for sparse
• MST is the foundation of many network optimization problems

What's Next: Huffman Coding

The next chapter shows greedy in data compression — Huffman coding assigns variable-length codes based on character frequency.

Practice Problems

| Problem | Platform | Key Insight | |---------|----------|-------------| | Network Delay Time | LeetCode 743 | Shortest path (Dijkstra), not MST | | Min Cost to Connect Points | LeetCode 1584 | MST on complete graph (Prim better) | | Connecting Cities | GeeksForGeeks | Standard MST application | | Minimum Spanning Tree | SPOJ | Test both Prim and Kruskal |