SimuVedaAlgorithms Lab Open in the lab

Graphs / Advanced

Prim's Minimum Spanning Tree Visualizer

Grow one tree from A. Always add the cheapest edge that reaches a node not yet in the tree.

Start the Prim's Minimum Spanning Tree simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(E log V)
Average timeO(E log V)
Worst timeO(E log V)
Extra spaceO(V + E)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Start the tree at A.
  2. Add A to the tree.
  3. Offer edge A–B (4).
  4. Offer edge A–C (2).
  5. The cheapest edge is A–C (2). Add C. Total = 2.
  6. Offer edge C–B (1).
  7. Offer edge C–D (8).
  8. Offer edge C–E (10).
  9. The cheapest edge is C–B (1). Add B. Total = 3.
  10. Offer edge B–D (5).
  11. B is already in the tree. Skip this edge.
  12. The cheapest edge is B–D (5). Add D. Total = 8.
  13. Offer edge D–E (2).
  14. Offer edge D–F (6).
  15. The cheapest edge is D–E (2). Add E. Total = 10.
  16. Offer edge E–F (3).
  17. The cheapest edge is E–F (3). Add F. Total = 13.
  18. F is already in the tree. Skip this edge.
  19. D is already in the tree. Skip this edge.
  20. E is already in the tree. Skip this edge.
  21. Done. Minimum spanning tree weight: 13.

Try it with your own input →

Prim's minimum spanning tree in Java, Python, C++, C and JavaScript

int prim(int src) {
  boolean[] inTree = new boolean[n];
  PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[2] - y[2]);
  pq.add(new int[]{-1, src, 0});
  int total = 0;
  while (!pq.isEmpty()) {
    int[] e = pq.poll(); int v = e[1];
    if (inTree[v]) continue;
    inTree[v] = true; total += e[2];
    for (int[] nb : adj[v])
      if (!inTree[nb[0]]) pq.add(new int[]{v, nb[0], nb[1]});
  }
  return total;
}
import heapq

def prim(adj, src):
    in_tree = [False] * len(adj)
    pq = [(0, src)]
    total = 0
    while pq:
        w, v = heapq.heappop(pq)
        if in_tree[v]:
            continue
        in_tree[v] = True; total += w
        for nb, nw in adj[v]:
            if not in_tree[nb]:
                heapq.heappush(pq, (nw, nb))
    return total
int prim(const vector<vector<pair<int,int>>>& adj, int src) {
  vector<bool> inTree(adj.size(), false);
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // (weight, node)
  pq.push({0, src});
  int total = 0;
  while (!pq.empty()) {
    auto [w, v] = pq.top(); pq.pop();
    if (inTree[v]) continue;
    inTree[v] = true; total += w;
    for (auto [nb, nw] : adj[v])
      if (!inTree[nb]) pq.push({nw, nb});
  }
  return total;
}
#include <limits.h>
#define MAXN 100
int n, w[MAXN][MAXN];   /* w[u][v] = edge weight, 0 = no edge */

/* Simple O(n^2) version: key[v] is the cheapest edge from the tree to v. */
int prim(int src) {
  int inTree[MAXN] = {0}, key[MAXN];
  for (int i = 0; i < n; i++) key[i] = INT_MAX;
  key[src] = 0;
  int total = 0;
  for (int round = 0; round < n; round++) {
    int v = -1;
    for (int i = 0; i < n; i++)
      if (!inTree[i] && (v < 0 || key[i] < key[v])) v = i;
    if (key[v] == INT_MAX) break;
    inTree[v] = 1; total += key[v];
    for (int nb = 0; nb < n; nb++)
      if (w[v][nb] && !inTree[nb] && w[v][nb] < key[nb]) key[nb] = w[v][nb];
  }
  return total;
}
// adj[v] = [[nb, w], ...]. A sorted array stands in for a priority queue.
function prim(adj, src) {
  const inTree = new Array(adj.length).fill(false);
  const pq = [[src, 0]];
  let total = 0;
  while (pq.length > 0) {
    pq.sort((x, y) => x[1] - y[1]);
    const [v, w] = pq.shift();
    if (inTree[v]) continue;
    inTree[v] = true; total += w;
    for (const [nb, nw] of adj[v])
      if (!inTree[nb]) pq.push([nb, nw]);
  }
  return total;
}

In an interview

LeetCode 1584, Min Cost to Connect All Points (Prim is often faster there because the graph is dense).

Prim looks like Dijkstra, but the priority is the edge weight alone, not the total distance from the start.

More graphs