Prim's algorithm

Prim's algorithm builds an MST by growing a single connected component from an arbitrary start vertex. At each step it adds the cheapest edge that connects a vertex already in the tree to one outside—the cut property guarantees this edge is safe. Implementation choices trade simplicity vs speed: an adjacency matrix plus linear scan each step gives O(V²); an adjacency list plus binary heap yields O(E log V) when E is moderate.

1) Idea

Maintain set S of vertices already in the partial tree. Initially S = { root }. Repeatedly choose the minimum‑weight edge (u, v) with u ∈ S and v ∉ S, add v and that edge. Stop after |V| − 1 edges (for a connected graph). For each vertex not yet in S, store in key[v] the cheapest edge weight from v to any vertex of S discovered so far; when v joins, relax its neighbors.

2) Arrays

• key[v] — minimum weight of an edge from v to the current tree (∞ until known).
• parent[v] — which tree vertex achieves that minimum (defines MST edges).
• in_mst[v] — whether v is already included.

Each iteration picks u ∉ S with smallest key[u], marks in_mst[u], then updates keys for neighbors of u.

3) Example graph

Same weighted K₄ as the minimum spanning tree lesson (unique MST total weight 6):

Vertices 0 … 3. Edge weights:

  0–1 : 1     2–3 : 2     0–3 : 3     1–2 : 4     0–2 : 5     1–3 : 6

4) C — Prim (adjacency matrix, O(V²))

Missing edges use INF; diagonal entries are zero.

#include <limits.h>
#include <stdio.h>

#define V 4
#define INF INT_MAX

static int adj[V][V];

static void edge(int a, int b, int w) {
    adj[a][b] = adj[b][a] = w;
}

static int min_key_vertex(const int key[], const int in_mst[]) {
    int best = -1;
    int best_k = INF;
    for (int i = 0; i < V; i++)
        if (!in_mst[i] && key[i] < best_k) {
            best_k = key[i];
            best = i;
        }
    return best;
}

/* Returns MST weight; builds tree from start; disconnected → partial sum */
long long prim_mst(int start) {
    int key[V], parent[V], in_mst[V];
    for (int i = 0; i < V; i++) {
        key[i] = INF;
        parent[i] = -1;
        in_mst[i] = 0;
    }
    key[start] = 0;

    long long total = 0;
    for (int cnt = 0; cnt < V; cnt++) {
        int u = min_key_vertex(key, in_mst);
        if (u < 0) break;   /* disconnected component */
        in_mst[u] = 1;
        if (parent[u] >= 0)
            total += (long long)adj[parent[u]][u];

        for (int v = 0; v < V; v++) {
            if (v == u || adj[u][v] == INF) continue;
            if (!in_mst[v] && adj[u][v] < key[v]) {
                key[v] = adj[u][v];
                parent[v] = u;
            }
        }
    }
    return total;
}

int main(void) {
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            adj[i][j] = (i == j) ? 0 : INF;

    edge(0, 1, 1); edge(2, 3, 2); edge(0, 3, 3);
    edge(1, 2, 4); edge(0, 2, 5); edge(1, 3, 6);

    printf("MST weight %lld\n", prim_mst(0));
    return 0;
}

5) Complexity

• Matrix + linear pick: O(V²) — good for dense graphs encoded as a full matrix.
• List + binary min‑heap: relax each edge at most once → O(E log V) typical time; Fibonacci heaps improve the theoretical bound but are rarely implemented in teaching code.
• Space: O(V) for Prim's arrays plus the graph storage.

6) Trace — root 0

Pick order and key[] over vertices 0–3 after each inclusion (∞ omitted as ∞ for readability).

MST edges: (0,1), (0,3), (2,3) — same weight as Kruskal on this graph (order of attachment may differ if keys tie).