Prim vs Kruskal, step by step.

Prim's and Kruskal's algorithms both find a minimum spanning tree (MST), the same one when all weights differ. Prim grows one tree from a start vertex, adding the lightest edge that leaves it. Kruskal sorts all the edges and adds each one that joins two separate trees. Use Prim on dense graphs, Kruskal on sparse graphs and edge lists.

Below, both run step by step on the same graph, so you can watch them take the same edges in a different order.

Prim vs Kruskal: what differs

Prim and Kruskal on the same graph

Both players run on the app's example 2: six vertices and ten weighted undirected edges, with the weights the Prim topic gives it. Prim starts at A and keeps a priority queue of candidate edges, at most one for each vertex outside the tree. When a lighter edge turns up to a vertex that already has an edge in the queue, it replaces that edge, five times on this graph. Prim adds AB, BE, EC, CF and FD, in that order, each time the lightest edge that leaves its tree.

Prim's algorithm from A on a weighted graph

All steps as text
  1. Consider a weighted undirected graph. Build its minimum spanning tree.
  2. Start from vertex A and explore its neighboring vertices.
  3. Vertex A's neighbors are B and D.
  4. Use a priority queue to keep candidate edges ordered by weight.
  5. Check the weight of edge AB: 71.
  6. Enqueue edge AB in the priority queue according to its weight.
  7. Check the weight of edge AD: 94.
  8. Enqueue edge AD in the priority queue according to its weight.
  9. After examining its neighbors, mark vertex A as inspected.
  10. Dequeue the minimum-weight edge AB and add it to the growing spanning tree (highlighted in yellow).
  11. Inspect vertex B, which is in the growing spanning tree but has not yet been inspected.
  12. Uninspected neighbors of vertex B: C, D and E.
  13. Check the weight of edge BC: 60.
  14. Enqueue edge BC in the priority queue according to its weight.
  15. Check the weight of edge BD: 79.
  16. BD (79) is lighter than AD (94), and both lead to D.
  17. Replace AD with BD in the queue.
  18. Check the weight of edge BE: 36.
  19. Enqueue edge BE in the priority queue according to its weight.
  20. After examining its neighbors, mark vertex B as inspected.
  21. Dequeue the minimum-weight edge BE and add it to the growing spanning tree (highlighted in yellow).
  22. Inspect vertex E, which is in the growing spanning tree but has not yet been inspected.
  23. Uninspected neighbors of vertex E: C and F.
  24. Check the weight of edge EC: 42.
  25. EC (42) is lighter than BC (60), and both lead to C.
  26. Replace BC with EC in the queue.
  27. Check the weight of edge EF: 87.
  28. Enqueue edge EF in the priority queue according to its weight.
  29. After examining its neighbors, mark vertex E as inspected.
  30. Dequeue the minimum-weight edge EC and add it to the growing spanning tree (highlighted in yellow).
  31. Inspect vertex C, which is in the growing spanning tree but has not yet been inspected.
  32. Uninspected neighbors of vertex C: D and F.
  33. Check the weight of edge CD: 68.
  34. CD (68) is lighter than BD (79), and both lead to D.
  35. Replace BD with CD in the queue.
  36. Check the weight of edge CF: 9.
  37. CF (9) is lighter than EF (87), and both lead to F.
  38. Replace EF with CF in the queue.
  39. After examining its neighbors, mark vertex C as inspected.
  40. Dequeue the minimum-weight edge CF and add it to the growing spanning tree (highlighted in yellow).
  41. Inspect vertex F, which is in the growing spanning tree but has not yet been inspected.
  42. Vertex F's only uninspected neighbor is D.
  43. Check the weight of edge FD: 64.
  44. FD (64) is lighter than CD (68), and both lead to D.
  45. Replace CD with FD in the queue.
  46. After examining its neighbors, mark vertex F as inspected.
  47. Dequeue the minimum-weight edge FD and add it to the growing spanning tree (highlighted in yellow).
  48. Inspect vertex D, which is in the growing spanning tree but has not yet been inspected.
  49. Since all other vertices have already been inspected, the minimum spanning tree is successfully constructed.
  50. The minimum spanning tree has the edges AB, BE, EC, CF and FD, with a total weight of 71 + 36 + 42 + 9 + 64 = 222.
Prim vs Kruskal — Prim's algorithm from A on a weighted graph. Last step: The minimum spanning tree has the edges AB, BE, EC, CF and FD, with a total weight of 71 + 36 + 42 + 9 + 64 = 222.

Kruskal sorts the edges and takes them lightest first, wherever they lie, while union-find, on the right, starts with every vertex as a set of its own. CF and BE come first and stand apart as two small trees until CE joins them; AB, the edge Prim took first, comes last. Both end with the same five edges, weighing 222 in all.

Kruskal's algorithm on the same graph

All steps as text
  1. Consider a weighted undirected graph. Build its minimum spanning tree by examining the edges in ascending order, starting with the lightest.
  2. Examine the edge CF.
  3. Use the Union-Find data structure to check whether the vertices C and F, connected by this edge, belong to the same set or different sets.
  4. Because its vertices belong to different sets, the edge CF cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  5. To reflect this, the roots of the sets containing vertices C and F are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  6. Examine the edge BE.
  7. Use the Union-Find data structure to check whether the vertices B and E, connected by this edge, belong to the same set or different sets.
  8. Because its vertices belong to different sets, the edge BE cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  9. To reflect this, the roots of the sets containing vertices B and E are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  10. Examine the edge CE.
  11. Use the Union-Find data structure to check whether the vertices C and E, connected by this edge, belong to the same set or different sets.
  12. Because its vertices belong to different sets, the edge CE cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  13. To reflect this, the roots of the sets containing vertices C and E are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  14. Examine the edge BC.
  15. Use the Union-Find data structure to check whether the vertices B and C, connected by this edge, belong to the same set or different sets.
  16. The edge BC is not added to the collection because its vertices already belong to the same set. Adding it would create a cycle.
  17. Examine the edge DF.
  18. Use the Union-Find data structure to check whether the vertices D and F, connected by this edge, belong to the same set or different sets.
  19. Because its vertices belong to different sets, the edge DF cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  20. To reflect this, the roots of the sets containing vertices D and F are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  21. Examine the edge DC.
  22. Use the Union-Find data structure to check whether the vertices D and C, connected by this edge, belong to the same set or different sets.
  23. The edge DC is not added to the collection because its vertices already belong to the same set. Adding it would create a cycle.
  24. Examine the edge AB.
  25. Use the Union-Find data structure to check whether the vertices A and B, connected by this edge, belong to the same set or different sets.
  26. Because its vertices belong to different sets, the edge AB cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  27. The roots of the sets containing vertices A and B are merged. With this step, the forest reaches V − 1 edges, forming a single spanning tree — the MST is complete.
  28. The minimum spanning tree has the edges CF, BE, CE, DF, AB, with a total weight of 9 + 36 + 42 + 64 + 71 = 222. The heavier edges BD, EF, AD were never examined.
Prim vs Kruskal — Kruskal's algorithm on the same graph. Last step: The minimum spanning tree has the edges CF, BE, CE, DF, AB, with a total weight of 9 + 36 + 42 + 64 + 71 = 222. The heavier edges BD, EF, AD were never examined.

Prim vs Kruskal at a glance

Prim's algorithm and Kruskal's algorithm solve the same problem: connect every vertex of a weighted undirected graph with the lightest possible set of edges, a minimum spanning tree. Both are greedy and never undo a choice. They differ in which edge counts as the next one.

PrimKruskal
GrowsOne tree, from a start vertexA forest of trees that merge
Next edgeThe lightest edge leaving the treeThe lightest remaining edge that joins two trees
Main structurePriority queueSorted edge list and union-find
Cycle checkNone neededUnion-find: are both ends in one tree?
TimeO(E log V) with a binary heap, O(V2) with an arrayO(E log E), the same as O(E log V)
Best onDense graphs, adjacency matricesSparse graphs, edge lists
Order aboveAB, BE, EC, CF, FDCF, BE, CE, DF, AB
Edges examined aboveAll 107: BD, EF and AD never
Disconnected graphSpans only the start vertex's partGives a minimum spanning forest

The players name an edge from either end: Kruskal's CE and DF are Prim's EC and FD.

One growing tree vs a merging forest

Both algorithms rest on the cut property: split the vertices into two groups in any way, and the lightest edge between the groups belongs to a minimum spanning tree. Prim applies it to the split between its tree and the rest of the graph, so its next edge is the lightest one leaving the tree, and the tree stays in one piece from the start vertex outward.

Kruskal applies it to the split between the tree at one end of an edge and the rest of the graph. When it reaches the lightest edge not yet examined, every lighter edge has been examined and has both ends in one tree, so if this edge joins two separate trees, no lighter edge leaves the tree at either end, and it is safe. Its trees can start anywhere: on the player's graph the first two edges, CF and BE, share no vertex. Kruskal starts with every vertex as a tree of its own, and two trees become one with every edge it keeps, so after V − 1 edges a single tree remains.

When no two weights are equal, the minimum spanning tree is unique, so both reach the same tree. With equal weights there can be several trees of the same total, and the two may pick different ones, depending on the start vertex and on how ties are ordered.

Why Kruskal needs union-find and Prim does not

Prim's next edge always has one end in the tree and one outside, so it can never close a cycle; all it tracks is which vertices are in the tree. Kruskal's next edge can lie anywhere, even between two vertices of one tree. On the player's graph, BC comes up after BE and CE have joined B and C through E, and DC after DF and CF have joined D and C through F: either would close a cycle. Union-find keeps each tree's vertices as one set under a root: two vertices are in the same tree when they have the same root, and keeping an edge puts one root under the other. With path compression and union by rank, each operation takes nearly constant time.

Prim needs its priority queue instead. On this graph the queue never holds more than three edges, one per vertex just outside the tree.

Prim vs Kruskal time and space complexity

Kruskal's running time is the sort: O(E log E), as the union-find work adds almost nothing. Since E is less than V2, log E is less than 2 log V, so that is the same as O(E log V). Prim with a binary heap also takes O(E log V), with a Fibonacci heap O(E + V log V), and with a plain array of candidate weights O(V2).

So on paper Prim with a heap and Kruskal tie, and the graph decides. On a dense graph, where E is close to its maximum, about V2/2, Prim's array version wins: it never touches a heap, while Kruskal must sort all of those edges. On a sparse graph, or one whose edges come as a list or are already sorted, Kruskal is simple and fast. On the players' graph Prim examined all ten edges, each once, while Kruskal, after sorting all ten, stopped examining them after seven, with the fifth tree edge.

Extra space is O(V) for Prim's queue, besides the graph; a lazy Prim, which queues every edge leaving the tree, needs O(E). Kruskal needs O(V) for its union-find and O(E) for the sorted edges.

When to use Prim and when to use Kruskal

Use Prim when the graph is dense or the tree should grow from one place:

  • Dense graphs and distance matrices: every pair of cities, sensors or pixels connected, where the array version runs in O(V2).
  • Graphs explored from a vertex: Prim follows the edges out of each new vertex and never needs them all at once.
  • Maze generation: a randomized Prim grows the maze outward from one cell.

Use Kruskal when the edges are what you have:

  • Sparse graphs and edge lists: roads, cables or pipes given as a list of connections with costs.
  • Clustering: stop when k trees remain, and they are k clusters with the widest gaps between them.
  • Disconnected graphs: one run gives a minimum spanning forest, a tree for each part.

Common mix-ups

  • Prim's start vertex changes the result. It changes the order of the edges. The total weight is always the same, and with distinct weights so is the tree.
  • Kruskal's tree is connected while it runs. It is a forest: after its first two edges here, CF and BE are two separate trees.
  • Kruskal examines every edge. It sorts them all, but stops examining once V − 1 edges are kept: here BD, EF and AD were sorted but never examined.
  • Prim is Dijkstra. The loop is the same, but Prim ranks a vertex by the weight of the single edge that joins it to the tree, and Dijkstra by its total distance from the source.
  • A minimum spanning tree gives shortest paths. It does not. Here the tree joins A and D by A, B, E, C, F, D, weighing 222, while the edge AD alone weighs 94.

Prim vs Kruskal interview questions

Which is faster, Prim or Kruskal?

Both run in O(E log V) with the usual structures, so it depends on the graph. On a dense graph, Prim with an array, in O(V2), is faster. On a sparse graph, or with edges already sorted, Kruskal is.

Why does Kruskal use union-find?

To tell whether an edge would close a cycle: it does exactly when both its ends are already in one tree. Union-find answers that by comparing the ends' roots, and merges the two trees when the edge is kept.

Do Prim's and Kruskal's algorithms work with negative weights?

Yes. A minimum spanning tree depends only on the order of the weights, and every spanning tree has V − 1 edges, so adding the same constant to every weight changes no choice. Shortest paths are different: there a negative weight can break Dijkstra's algorithm.

What do they return on a disconnected graph?

Kruskal returns a minimum spanning forest, a tree for each connected part. Prim spans only the part that holds its start vertex; it has to be run again from a vertex it never reached.

When can Prim and Kruskal return different trees?

Only when some weights are equal. Then several spanning trees can share the minimum total, and which one each algorithm finds depends on the start vertex and the order of ties. The total weight is always the same.

One graph here.
Both algorithms in the app.

In VisiGrab, Prim and Kruskal each have a topic on the same four example graphs, and the Graph Constructor runs either one on a graph you draw.

Four graphs, two weightings

Both topics use the same four six-vertex layouts, each with weights of its own. Prim shows its priority queue of candidate edges beside the graph, and Kruskal its union-find sets as they merge.

Prim or Kruskal, one switch

In the Graph Constructor, choose MST, draw an undirected graph of up to 12 vertices with weights from 1 to 99 and tap Apply. Each Next adds one tree edge; a switch changes the algorithm, and a disconnected graph is refused.

Theory for both

Prim's info dialog sets six spanning trees of one graph side by side and compares O(V2) with O(E log V). Kruskal's walks through four stages in six pictures, ends with a summary against Prim and adds up O(E log E).

Python, Java and C++

Prim with an in-tree set and an edge queue that swaps in a lighter edge; Kruskal sorting the edges and merging sets until V − 1 edges are kept. Each links to its full source on GitHub.

Two quizzes

Nine questions on Prim and eight on Kruskal, with an explanation for every option.

Union-Find too

The structure behind Kruskal's cycle check has a topic of its own: tap two of nine nodes to merge their sets.

One tree or many,
the same minimum.

Download VisiGrab to watch Prim's queue and Kruskal's forest at work, then draw a graph of your own and switch between them.

Prim and Kruskal each have a topic among 30+. See them all