DSA · Patterns, not puzzles

How do you find a minimum spanning tree?

HardmstkruskalprimUpdated Oct 2026

Short answer

Kruskal sorts edges by weight and adds the cheapest edge that does not create a cycle, using union-find. Prim grows a tree from one vertex by repeatedly adding the cheapest edge that connects a new vertex.

A minimum spanning tree connects every vertex with the smallest possible total edge weight. It applies to undirected weighted graphs. Both Kruskal and Prim are greedy, but they make the choice from different perspectives: global edge order versus a growing frontier.

function kruskal(nodes, edges) {
  const parent = new Map(nodes.map((node) => [node, node]));
  const rank = new Map(nodes.map((node) => [node, 0]));

  function find(node) {
    if (parent.get(node) !== node) {
      parent.set(node, find(parent.get(node)));
    }
    return parent.get(node);
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return false;
    if (rank.get(rootA) < rank.get(rootB)) {
      parent.set(rootA, rootB);
    } else if (rank.get(rootA) > rank.get(rootB)) {
      parent.set(rootB, rootA);
    } else {
      parent.set(rootB, rootA);
      rank.set(rootA, rank.get(rootA) + 1);
    }
    return true;
  }

  const sorted = [...edges].sort((a, b) => a.weight - b.weight);
  const result = [];
  let total = 0;

  for (const edge of sorted) {
    if (union(edge.from, edge.to)) {
      result.push(edge);
      total += edge.weight;
    }
  }

  return { edges: result, total };
}

Kruskal skips an edge when both endpoints are already in the same set, which would create a cycle.

Kruskal versus Prim

Kruskal: sort edges, O(E log E), good for sparse graphs and edge lists
Prim: grow one tree, O(E log V) with a heap, good for dense graphs
Both produce a minimum spanning tree, not necessarily the same one
If the graph is disconnected, they produce a minimum spanning forest
A spanning tree on V vertices has exactly V - 1 edges

The cut property justifies both algorithms: for any cut, the cheapest edge crossing the cut belongs to some minimum spanning tree. Each greedy choice respects this property, which is why the local choice is globally safe.

A minimum spanning tree minimizes the sum of edge weights, not the shortest path between two vertices. Those are different problems and can produce different trees.

Follow-ups you should expect

Interviewers use these to check whether the first answer was understanding or memorisation.

1Why does Kruskal's algorithm use union-find?
2When would you choose Prim over Kruskal?
3What happens if the graph is disconnected?
4How many edges does a spanning tree have?

Say it in the interview

Kruskal sorts all edges by weight and adds an edge only if it connects two different components, which I track with union-find. Prim starts from one vertex and repeatedly adds the cheapest edge that reaches a new vertex, usually with a priority queue. Both are greedy and justified by the cut property. Kruskal is convenient for sparse graphs and edge lists, while Prim is often better for dense graphs.

Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.

Now say it out loud.

Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.

Start a free DSA interview Browse all questions

Kruskal versus Prim

Follow-ups you should expect

Related questions

Now say it out loud.