Graphs and Network Algorithms · Minimum Spanning Trees

Prim's Algorithm

Prim's algorithm grows a minimum spanning tree outward from a starting vertex by repeatedly choosing the cheapest crossing edge.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

We teach Prim as the vertex-frontier view of minimum spanning trees.

Guided Lesson Notes

Understanding Prim's Algorithm

Prim's Algorithm focuses on relationships, reachability, paths, cycles, connectivity, and optimization over edges. Prim's algorithm grows a minimum spanning tree outward from a starting vertex by repeatedly choosing the cheapest crossing edge.

Model: draw vertices as dots and edges as connections; then decide whether direction, weight, or capacity matters.

Invariant: visited, distance, parent, component, or flow arrays must match what has actually been discovered so far.

Implementation: adjacency lists or matrices, queues, stacks, priority queues, union-find, and repeated edge relaxation.

Use Prim's Algorithm when the problem mentions roads, networks, prerequisites, components, shortest paths, spanning costs, or dependency order.

Visual Model

A small picture for Prim's Algorithm

Key Ideas

Growing tree frontier
Priority queue edge choice
Cut intuition

Practice Prompts

Trace Prim from two different starting vertices.
Compare Prim and Kruskal on the same graph.

Vocabulary

Terms students should be able to say clearly

Vertex

An object or state in the graph.

Edge

A relationship or move between vertices.

Path

A sequence of edges from one vertex to another.

Cycle

A path that returns to a previous vertex.

Component

A group of vertices connected by reachability.

Relaxation

Trying to improve a known distance or cost through an edge.

Worked Example

Worked example: tracing Prim's Algorithm

Trace a small input, focusing on growing tree frontier.

1Write a small input where Prim's Algorithm is clearly useful.
2Label the part of the input related to Growing tree frontier.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Adjacency-list traversal	O(V + E)	DFS and BFS visit vertices and inspect edges.
Adjacency matrix storage	O(V^2)	A matrix reserves space for every possible pair.
Weighted optimization	Varies	MST and shortest-path algorithms depend on sorting, heaps, and graph density.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Prim's Algorithm interview problem: Minimum Cost to Connect All Cities

Interview medium

Problem

Given possible undirected connections between cities, find the minimum total cost to connect every city.

Input

The first line contains n and m. The next m lines contain u v cost using 1-based city labels.

Output

Print the minimum cost, or -1 if the graph cannot be fully connected.

Sample Input

Sample Output

Why the sample works

The minimum spanning tree uses costs 1, 2, and 3 for a total of 6.

Approach

1Sort all connections by cost.
2Use union-find to avoid cycles.
3Take an edge only if it connects two different components.
4The graph is connected only if exactly n - 1 edges are chosen.

O(m log m) time and O(n) extra space.

Java Solution

import java.util.*;

public class Main {
  static class DSU {
    int[] parent;
    int[] rank;

    DSU(int n) {
      parent = new int[n + 1];
      rank = new int[n + 1];
      for (int i = 1; i <= n; i++) parent[i] = i;
    }

    int find(int x) {
      if (parent[x] != x) parent[x] = find(parent[x]);
      return parent[x];
    }

    boolean union(int a, int b) {
      int ra = find(a);
      int rb = find(b);
      if (ra == rb) return false;
      if (rank[ra] < rank[rb]) {
        parent[ra] = rb;
      } else if (rank[ra] > rank[rb]) {
        parent[rb] = ra;
      } else {
        parent[rb] = ra;
        rank[ra]++;
      }
      return true;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[][] edges = new int[m][3];
    for (int i = 0; i < m; i++) {
      edges[i][0] = sc.nextInt();
      edges[i][1] = sc.nextInt();
      edges[i][2] = sc.nextInt();
    }

    Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
    DSU dsu = new DSU(n);
    int used = 0;
    long cost = 0;

    for (int[] edge : edges) {
      if (dsu.union(edge[0], edge[1])) {
        used++;
        cost += edge[2];
      }
    }

    System.out.println(used == n - 1 ? cost : -1);
  }
}

Python Solution

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
edges.sort(key=lambda x: x[2])

parent = list(range(n + 1))
rank = [0] * (n + 1)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    elif rank[ra] > rank[rb]:
        parent[rb] = ra
    else:
        parent[rb] = ra
        rank[ra] += 1
    return True

used = 0
cost = 0
for u, v, w in edges:
    if union(u, v):
        used += 1
        cost += w

print(cost if used == n - 1 else -1)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Prim's Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free Session Text Us Open Online Compiler