Skip to content
Hello Python
Algorithm1 Practice2 Interview

Prim

Grow a minimum spanning tree by repeatedly choosing the cheapest edge leaving the tree. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Prim when the prompt's constraints and required operations match this shape: Grow a minimum spanning tree by repeatedly choosing the cheapest edge leaving the tree.

Pybit demonstrates Prim in a professional Python interview workspace.
On this page · Grow One Connected Tree

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Prim Code Labs

Grow One Connected Tree

Prim starts from one vertex and grows a connected visited set. At every step it chooses the cheapest edge crossing from the tree to an unvisited vertex.

Push Crossing Edges onto a Heap

When a vertex joins, push its outgoing edges whose other endpoint is not yet visited. The heap may contain obsolete entries as the cut changes.

Trace Prim Frontier Choices

Reference
import heapq

def prim_trace(adjacency,start):
    heap=[(0,start)];visited=set();total=0;trace=[]
    while heap:
        weight,node=heapq.heappop(heap)
        if node in visited:continue
        visited.add(node);total+=weight;trace.append([node,weight,total])
        for neighbor,cost in adjacency[node]:
            if neighbor not in visited:heapq.heappush(heap,(cost,neighbor))
    return trace
Practice

Implement prim_trace(adjacency,start). Edges are [neighbor,weight]; return [node,weight,total] for accepted heap entries.

Public tests

  • Accept the cheapest crossing edge

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Skip Vertices Already in the Tree

A popped edge to an already visited vertex would create a cycle, so skip it. The first accepted heap edge for an unvisited vertex is safe by the cut property.

Compute Prim MST Weight

Reference
import heapq

def prim_weight(adjacency):
    if not adjacency:return 0
    heap=[(0,0)];visited=set();total=0
    while heap:
        weight,node=heapq.heappop(heap)
        if node in visited:continue
        visited.add(node);total+=weight
        for neighbor,cost in adjacency[node]:
            if neighbor not in visited:heapq.heappush(heap,(cost,neighbor))
    return total if len(visited)==len(adjacency) else None
Practice

Implement prim_weight(adjacency). Return MST weight from node zero or None if disconnected.

Public tests

  • Reject a disconnected frontier

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Prim or Kruskal

Choose Prim for adjacency-list graphs and connected growth, especially dense graphs with suitable priority structures. Choose Kruskal when edges are already sorted or sparse and union-find is natural.

Explain It in an Interview

Say: “Visited vertices define a cut. The heap’s cheapest live crossing edge is safe, and an already visited endpoint would create a cycle.” Check visited count for disconnection and state O(E log V) heap time.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Prim complete workflowO(E log E)O(E log E)Grow from node zero using the lightest edge crossing from visited to unvisited vertices.

Space

O(V + E) for the focused Grow a Spanning Tree with Prim implementation.

Assumptions

  • At each step the heap minimum crossing edge is safe by the cut property. Adding its new endpoint preserves a tree; reaching every vertex yields an MST.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Prim invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The selected edges remain acyclic.
  3. Each accepted edge reduces the number of disconnected tree components by one.
  4. Keep only crossing edges on a min-heap frontier. Preserve this claim after every transition.
  5. Count each vertex when it first joins the tree. Preserve this claim after every transition.

When To Use Or Avoid Prim

Use It When

  • Use Prim when this precondition is stated or can be proved: The weighted graph is undirected, and the required output connects each component without cycles.
  • Use it when this maintained state removes repeated work: The selected edges remain acyclic.

Choose Another Tool When

  • Avoid Prim when this precondition is absent: The weighted graph is undirected, and the required output connects each component without cycles.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The weighted graph is undirected, and the required output connects each component without cycles.

Avoid

def prim_spanning_weight(node_count, edges):
    pass

Use instead

def prim_spanning_weight(node_count, edges):
    import heapq
    if node_count <= 1:
        return 0
    graph = [[] for _ in range(node_count)]
    for left, right, weight in edges:
        graph[left].append((weight, right)); graph[right].append((weight, left))
    visited = set()
    frontier = [(0, 0)]
    total = 0
    while frontier and len(visited) < node_count:
        weight, node = heapq.heappop(frontier)
        if node in visited:
            continue
        visited.add(node); total += weight
        for next_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(frontier, (next_weight, neighbor))
    return total if len(visited) == node_count else -1

Where you will hit this: Grow a Spanning Tree with Prim(opens in a new tab)

Breaking the state transition

Returns the first edge weight instead of growing through every vertex.

Prevent it: Preserve this proof obligation: The cut property makes each chosen minimum crossing edge compatible with some minimum spanning tree.

Avoid

def prim_spanning_weight(n,edges):
    return min((w for _,_,w in edges),default=0)

Use instead

def prim_spanning_weight(node_count, edges):
    import heapq
    if node_count <= 1:
        return 0
    graph = [[] for _ in range(node_count)]
    for left, right, weight in edges:
        graph[left].append((weight, right)); graph[right].append((weight, left))
    visited = set()
    frontier = [(0, 0)]
    total = 0
    while frontier and len(visited) < node_count:
        weight, node = heapq.heappop(frontier)
        if node in visited:
            continue
        visited.add(node); total += weight
        for next_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(frontier, (next_weight, neighbor))
    return total if len(visited) == node_count else -1

Where you will hit this: Grow a Spanning Tree with Prim(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(E log E).

Avoid

def prim_spanning_weight(n,edges):
    return min((w for _,_,w in edges),default=0)

Use instead

def prim_spanning_weight(node_count, edges):
    import heapq
    if node_count <= 1:
        return 0
    graph = [[] for _ in range(node_count)]
    for left, right, weight in edges:
        graph[left].append((weight, right)); graph[right].append((weight, left))
    visited = set()
    frontier = [(0, 0)]
    total = 0
    while frontier and len(visited) < node_count:
        weight, node = heapq.heappop(frontier)
        if node in visited:
            continue
        visited.add(node); total += weight
        for next_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(frontier, (next_weight, neighbor))
    return total if len(visited) == node_count else -1

Where you will hit this: Maximum Container Area(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.