Prim's algorithm: time and space complexity

Medium interview relevanceRoadmap: Advanced

Time	O(E log V) with a binary heap; O(V²) with an array
Space	O(V + E)

Why it costs this much

Each edge can enter the heap, and each heap operation costs O(log V).

Code

import heapq
def prim(graph, start):                    # graph[u] = [(v, w), ...] for every vertex
    seen, total = set(), 0
    heap = [(0, start)]
    while heap and len(seen) < len(graph):
        w, u = heapq.heappop(heap)         # O(log E) per pop
        if u in seen:
            continue
        seen.add(u)
        total += w
        for v, wt in graph[u]:             # each edge is pushed at most twice
            if v not in seen:
                heapq.heappush(heap, (wt, v))
    return total

Common pitfalls

It assumes a connected, undirected graph. Skip vertices that are already in the tree when you pop them.

Operation by operation

Operation	Best	Average	Worst	Space
Prim minimum spanning tree	O(E log V)	O(E log V)	O(E log V)	O(V + E) with lazy deletion; O(V) with decrease-key

Prim minimum spanning tree. Binary heap and an adjacency list. With an array and no heap it is O(V²), which can win on dense graphs.