Prim's Algorithm

Tags

Prim's Algorithm

Category

Famous Algorithms

Difficulty

Very Hard

Problem Statement

Given a connected, undirected, weighted graph, find the minimum spanning tree (MST) -- the subset of edges that connects all vertices with the minimum total edge weight, without forming any cycles. Prim's algorithm builds the MST by greedily adding the cheapest edge that connects a visited vertex to an unvisited vertex.

Intuition

Prim's algorithm is based on the cut property of MSTs: for any cut of the graph (a partition of vertices into two non-empty sets), the lightest edge crossing the cut is in some MST. The algorithm maintains a growing set S of visited vertices. At each step, the cheapest edge from S to V - S is added, and the newly connected vertex joins S. A min-heap (priority queue) efficiently retrieves the cheapest crossing edge.

Approach

  1. Initialize: pick an arbitrary starting vertex. Add it to the visited set S. Push all its edges into a min-heap keyed by edge weight.
  2. While the heap is non-empty and |S| < |V|:
    • Extract the minimum-weight edge (u, v, w) from the heap.
    • If v is already in S, skip (it would form a cycle).
    • Otherwise, add v to S, add edge (u, v, w) to the MST.
    • Push all edges from v to unvisited neighbors into the heap.
  3. When |S| = |V|, the MST is complete. The collected edges form the MST.

Pseudocode

function primsAlgorithm(graph, startVertex):
    n = number of vertices
    visited = set containing startVertex
    mstEdges = []
    totalWeight = 0
    minHeap = empty min-heap

    // Push all edges from startVertex
    for (neighbor, weight) in graph[startVertex]:
        minHeap.push((weight, startVertex, neighbor))

    while minHeap is not empty and |visited| < n:
        (weight, u, v) = minHeap.pop()
        if v in visited:
            continue
        visited.add(v)
        mstEdges.append((u, v, weight))
        totalWeight += weight
        for (neighbor, w) in graph[v]:
            if neighbor not in visited:
                minHeap.push((w, v, neighbor))

    return mstEdges, totalWeight

Time & Space Complexity

  • Time: O(E log E) or equivalently O(E log V) since E <= V^2. Each edge is pushed onto the heap at most twice (once from each endpoint), and each heap operation is O(log E).
  • Space: O(V + E). The heap can hold up to O(E) edges. The visited set and MST edges are O(V).

With an indexed priority queue (decrease-key), the complexity can be improved to O(E + V log V) using a Fibonacci heap, though this is rarely done in practice.

Key Insights

  • Prim's algorithm is greedy: at each step, it takes the cheapest edge crossing the cut between visited and unvisited vertices. The cut property guarantees correctness.
  • The algorithm is similar to Dijkstra's algorithm in structure (both use a priority queue and grow a set of "processed" nodes), but they optimize different things: Prim's minimizes edge weight; Dijkstra's minimizes distance from source.
  • Prim's is well-suited for dense graphs (especially with an adjacency matrix and O(V^2) simple implementation), whereas Kruskal's (sort all edges, union-find) tends to be preferred for sparse graphs.
  • The MST of a connected graph with V vertices always has exactly V - 1 edges.
  • If the graph is not connected, Prim's from a single start vertex finds the MST of the connected component containing that vertex.

Edge Cases

  • Single vertex: The MST is empty (no edges needed).
  • Graph with one edge: That edge is the MST.
  • All edges have equal weight: Any spanning tree is an MST.
  • Disconnected graph: Prim's from one vertex only spans its connected component. Run it from each unvisited vertex to get a minimum spanning forest.
  • Negative edge weights: Prim's handles negative weights correctly, unlike Dijkstra's with negative edges.
  • Parallel edges (multigraph): The algorithm naturally picks the cheapest among parallel edges.
  • Self-loops: These are never part of an MST and are naturally skipped (the endpoint is already visited).

Linked mentions