Minimum Spanning Tree

What a minimum spanning tree actually is

Given a connected, undirected, weighted graph on n vertices, a spanning tree is any subset of n−1 edges that keeps every vertex reachable — connected, acyclic, nothing left out. The minimum spanning tree is the spanning tree whose weights sum to the smallest possible total. Notice what is not being minimised: not the distance between any particular pair of vertices, only the total weight of the whole structure. An MST can easily make the trip from u to v much longer than the graph allows — it only promises the cheapest total wiring.

Why greedy is safe: the cut property

Greedy algorithms usually need a proof before you trust them, and MST has a clean one. Split the vertices into two non-empty groups — call that a cut. The cut property says: the cheapest edge crossing that cut belongs to some MST. The intuition is an exchange argument. Suppose an MST T doesn't contain that cheapest crossing edge e. Add e to T anyway — now you have a cycle, and that cycle has to cross back over the cut on some other edge f. Since e was the cheapest crossing edge, weight(e) ≤ weight(f), so swapping f out for e leaves you with a spanning tree that is no heavier. The greedy choice was never a mistake.

The mirror image is the cycle property: on any cycle, the single heaviest edge is never needed — you can always delete it and stay connected. These two facts are the same fact seen from opposite ends, and they generate the two classic algorithms. Kruskal thinks in cycles ("take the cheapest edge unless it closes a cycle"), Prim thinks in cuts ("keep taking the cheapest edge leaving the tree I've built so far").

On uniqueness: if all edge weights are distinct, the MST is unique — the exchange argument above becomes a strict inequality and no swap can tie. With ties, several different MSTs can exist, but every one of them has the same total weight. That's the honest answer to "is the MST unique?" in an interview: the tree may not be, the cost always is.

Kruskal's algorithm: sort every edge, take it if it doesn't close a cycle

Kruskal is the cycle property applied greedily. Sort all E edges by weight, walk them cheapest first, and accept an edge only when its two endpoints are currently in different components. "Different components?" is exactly the question the union-find structure from the previous chapter answers in near-constant time — here is a compact version with path halving and union by rank so this file stands alone.

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // path halving — flatten as we climb
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false; // already connected — this edge would close a cycle
    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
    return true;
  }
}

// edges: [u, v, weight][] with 0-indexed vertices — O(E log E) time, O(V) extra space
function kruskalMST(n, edges) {
  const sorted = [...edges].sort((a, b) => a[2] - b[2]); // the sort IS the algorithm's cost; the copy leaves the caller's edges in order

  const dsu = new DSU(n);
  const tree = [];
  let total = 0;

  for (const [u, v, w] of sorted) {
    if (dsu.union(u, v)) { // union returns false when u and v already share a root
      tree.push([u, v, w]);
      total += w;
      if (tree.length === n - 1) break; // n-1 edges = spanning, stop early
    }
  }

  // fewer than n-1 accepted edges means the graph was disconnected
  return tree.length === n - 1 ? { total, tree } : null;
}

Complexity is O(E log E) dominated entirely by the sort — the union-find work is O(E · α(V)), and the inverse Ackermann function α is below 5 for any input that fits in memory, so treat it as constant when you say the number out loud. Space is O(V) for the DSU (the edge list is given, not built). Since E ≤ V², log E ≤ 2 log V, so you'll also see this written O(E log V) — same thing.

Watching Kruskal build the tree, edge by edge

Running it on the graph above, with edges sorted 1, 2, 3, 4, 5, 6, 7:

Prim's algorithm: grow one tree outward with a heap

Prim keeps a single growing tree instead of a forest. At each step the cut is "vertices in the tree" versus "vertices outside," and the cut property says to take the cheapest edge crossing it. A min-heap keyed by edge weight produces that edge in O(log E). Here is a compact binary heap of [weight, from, to] triples so the code below runs as written.

class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }
  push(item) {
    const a = this.a;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1, r = l + 1;
        let s = i;
        if (l < a.length && a[l][0] < a[s][0]) s = l;
        if (r < a.length && a[r][0] < a[s][0]) s = r;
        if (s === i) break;
        [a[s], a[i]] = [a[i], a[s]];
        i = s;
      }
    }
    return top;
  }
}

// adj[u] = [[v, weight], ...] — O(E log V) time, O(E) space for the heap
function primMST(n, adj) {
  const inTree = new Array(n).fill(false);
  const heap = new MinHeap();
  const tree = [];
  let total = 0;

  inTree[0] = true; // seed with any vertex — MST is the same regardless of start
  for (const [v, w] of adj[0]) heap.push([w, 0, v]);

  while (heap.size > 0 && tree.length < n - 1) {
    const [w, u, v] = heap.pop();
    if (inTree[v]) continue; // STALE entry — v got absorbed by a cheaper edge already

    inTree[v] = true;
    tree.push([u, v, w]);
    total += w;

    for (const [next, nw] of adj[v]) {
      if (!inTree[next]) heap.push([nw, v, next]); // only frontier edges matter
    }
  }

  return tree.length === n - 1 ? { total, tree } : null;
}

Dry run: primMST(5, adj) on the same A–B–C–D–E graph, starting at A

Prim lands on the identical total (11) and even the identical edge set as Kruskal's table above, just discovered in a different order — Kruskal sorts globally first, Prim only ever looks at the cheapest edge leaving its current tree. The stale pop at step 4 (A–D, weight 4) is exactly why the heap can hold more entries than vertices: D found a cheaper route through B before its direct edge from A was ever popped.

Prim also gives the wrong answer silently on a disconnected graph: it fills one component and stops. Kruskal's loop, by contrast, naturally builds a minimum spanning forest — one tree per component (the version above returns null because of its final n - 1 check; return tree without that check to get the forest). If the input might be disconnected and you're using Prim, you must loop over unvisited seeds yourself, or check tree.length === n - 1 as above.

Kruskal vs Prim: which one in the interview

The one that actually decides interviews is the last row of the dense column. When the graph is implicit and complete — "n points, cost between any two is their distance" — materialising all V²/2 edges to sort them is the mistake. With V = 1000 that's half a million edges to build and sort when O(V²) Prim never stores a single one.

Min Cost to Connect All Points — the dense case done right

The classic version: given points on a plane, connecting two costs their Manhattan distance, connect them all as cheaply as possible. Every pair is an edge, so this is a complete graph — reach for O(V²) Prim, which keeps one number per vertex ("cheapest known edge from the tree to you") and rescans instead of heaping.

// O(V²) time, O(V) space — never builds the edge list at all
function minCostConnectPoints(points) {
  const n = points.length;
  const minDist = new Array(n).fill(Infinity);
  const inTree = new Array(n).fill(false);
  minDist[0] = 0; // start vertex costs nothing to attach
  let total = 0;

  for (let step = 0; step < n; step++) {
    // pick the cheapest vertex still outside the tree — this is the cut property
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!inTree[v] && (u === -1 || minDist[v] < minDist[u])) u = v;
    }

    inTree[u] = true;
    total += minDist[u];

    // relax: u joining the tree may give every outsider a cheaper attachment
    for (let v = 0; v < n; v++) {
      if (inTree[v]) continue;
      const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
      if (d < minDist[v]) minDist[v] = d;
    }
  }
  return total;
}

The relax step is why this works without a heap: minDist[v] is always "cheapest edge from the current tree to v," so scanning it for the minimum is finding the cheapest edge across the cut. That linear scan costs O(V) per step for O(V) steps — the same O(V²) as building the matrix, so the heap buys nothing.

The virtual-node trick, and other MST disguises

MST problems rarely announce themselves. A recurring twist: each node has a standalone cost as well as connection costs — "each village can dig its own well for cost w[i], or lay a pipe to another village for cost c." That looks like it isn't a spanning tree at all, until you add a virtual node 0 representing "the water source" and connect it to village i with weight w[i]. Now "dig a well" is just another edge, and a plain MST over n+1 nodes is the answer.

function minCostToSupplyWater(n, wells, pipes) {
  // vertex 0 is virtual: edge 0→i with cost wells[i-1] means "dig a well at i"
  const edges = pipes.slice();
  for (let i = 0; i < n; i++) edges.push([0, i + 1, wells[i]]);

  const result = kruskalMST(n + 1, edges); // n+1 vertices now, so n edges in the tree
  return result.total;
}

Dry run: minCostToSupplyWater(3, [1, 2, 2], [[1, 2, 1], [2, 3, 1]])

Village 1 has a cheap well (1), villages 2 and 3 have dearer wells (2 each), and two pipes cost 1 apiece. With the virtual vertex 0 added, the edge list is the two pipes followed by 0–1 (1), 0–2 (2) and 0–3 (2). Sorting is stable, so equal weights keep their input order:

The plan it found: dig one well at village 1 and run pipes 1–2 and 2–3, for 1 + 1 + 1 = 3. Digging all three wells would cost 5. In the tree every village has a path to vertex 0 whose last edge is a well, so each village is supplied by a chain of pipes from a village that has a well.

Two more disguises worth recognising instantly. "Remove the maximum number of edges while keeping the graph connected" → build an MST, the answer is E − (V−1). "Minimise the largest edge on a path between all pairs" → the MST is also a minimax spanning tree, so the answer is the heaviest edge on the MST path, not a shortest-path computation.

Maximum spanning tree: negate the weights

Some problems want the heaviest wiring that still connects everything: the most reliable links, the widest pipes, the highest total capacity. Both properties flip cleanly. The heaviest edge crossing any cut belongs to some maximum spanning tree, and the lightest edge on any cycle is never needed. You do not need a second algorithm. Every spanning tree has exactly n−1 edges, so negating every weight multiplies every tree's total by −1 and reverses the ranking of the trees: the tree with the smallest negated total is the tree with the largest original total.

function maxSpanningTreeWeight(n, edges) {
  const flipped = edges.map(([u, v, w]) => [u, v, -w]);
  const result = kruskalMST(n, flipped); // the same function as above, untouched
  return result === null ? null : -result.total; // flip the sign back
}

This works because Kruskal only compares weights; it never relied on them being positive, unlike Dijkstra. For the same reason you can add one constant to every weight, or subtract one, without changing which tree Kruskal picks: all spanning trees contain the same number of edges, so every total moves by the same amount. Sorting in descending order and keeping the rest of the loop is the equivalent one-line change.

Why the MST path is also the minimax path

The warning at the top said an MST route between two vertices need not be the cheapest route. It is still the best route by a different measure. Define the bottleneck of a path as its single heaviest edge. For any two vertices u and v, the path between them inside the MST has the smallest bottleneck of all u–v paths in the whole graph.

Here is the proof, using nothing but the cut property. Let e = (a, b) be the heaviest edge on the tree path from u to v, and suppose some other path P in the graph had a bottleneck lighter than w(e). Delete e from the tree: the tree falls into two pieces, and because e was on the tree path, u is in one piece and v is in the other. P walks from u to v, so at least one of its edges f crosses between the two pieces. Then w(f) ≤ bottleneck(P) < w(e), and swapping e for f gives a spanning tree that is strictly lighter than the MST. That is a contradiction, so no such P exists.

This turns a family of problems into union-find. If you only need the bottleneck between two specific vertices, run Kruskal's sweep and stop the moment u and v land in the same component: the weight of the edge you just accepted is the answer. You never need the tree itself.

Path with minimum effort: Kruskal over the grid edges

Given a grid of heights, the effort of a route is the largest absolute height difference between consecutive cells, and you want the route from the top-left to the bottom-right with the least effort. The graph is the grid itself: each cell is a vertex, each pair of neighbours is an edge, and the weight is the height difference. "Smallest possible largest edge on a path" is exactly the bottleneck from the last section, so the answer is the weight of the edge that first connects the two corners in a Kruskal sweep. (The shortest-path version of this problem is the Dijkstra exercise in the graph chapter; the two solutions are worth writing side by side.)

// O(RC log RC) time for R rows and C columns, O(RC) space
function minimumEffortPath(heights) {
  const rows = heights.length, cols = heights[0].length;
  if (rows * cols === 1) return 0; // start is already the finish

  const edges = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const id = r * cols + c; // flatten (r, c) into one vertex number
      if (c + 1 < cols) edges.push([id, id + 1, Math.abs(heights[r][c] - heights[r][c + 1])]);
      if (r + 1 < rows) edges.push([id, id + cols, Math.abs(heights[r][c] - heights[r + 1][c])]);
    }
  }
  edges.sort((a, b) => a[2] - b[2]);

  const dsu = new DSU(rows * cols);
  for (const [u, v, w] of edges) {
    dsu.union(u, v);
    if (dsu.find(0) === dsu.find(rows * cols - 1)) return w; // the corners just connected: w is the bottleneck
  }
  return 0; // unreachable: a grid is connected
}

Each cell contributes at most two edges (right and down), which covers every neighbouring pair once, so there are fewer than 2RC edges and the sort dominates. Running it on [[1,2,2],[3,8,2],[5,3,5]], with cells numbered 0 to 8 row by row:

The route it found is 0 → 3 → 6 → 7 → 8, down the left side and across the bottom, with every step costing 2. The heavier edges (3, 5, 6) are never looked at: the sweep stops as soon as the answer is known.

Edge-length limited paths: sort the queries too

Here is a more general shape. You have one fixed graph and many queries [p, q, limit], each asking "is there a path from p to q whose every edge is strictly shorter than limit?" Answering each query with its own search is O(Q · (V + E)). The bottleneck fact above says a query is yes exactly when p and q are connected using only edges lighter than the limit, and a union-find can maintain exactly that, provided edges are only ever added.

Union-find cannot delete, so you cannot sweep the limit downward. Sweep it upward instead. Sort the edges once by weight, sort the queries by limit, and walk the queries from smallest limit to largest: before answering a query, union every edge whose weight is below its limit. The set of unioned edges only grows, which is what the structure supports. Because you reordered the queries, record each one's original index and write its answer there.

// O(E log E + Q log Q) time, O((E + Q) α(V)) for the unions and finds
function distanceLimitedPathsExist(n, edgeList, queries) {
  const edges = [...edgeList].sort((a, b) => a[2] - b[2]);
  const order = queries.map((_, i) => i).sort((a, b) => queries[a][2] - queries[b][2]);

  const dsu = new DSU(n);
  const answer = new Array(queries.length).fill(false);
  let next = 0; // edges[0..next-1] are already unioned

  for (const qi of order) {
    const [p, q, limit] = queries[qi];
    while (next < edges.length && edges[next][2] < limit) { // strictly shorter than the limit
      dsu.union(edges[next][0], edges[next][1]);
      next++;
    }
    answer[qi] = dsu.find(p) === dsu.find(q); // answer goes back to the ORIGINAL position
  }
  return answer;
}

Dry run: n = 3, edges [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries [[0,1,2],[0,2,5]]

The result is [false, true]. Note the first query's edge 0–1 has weight exactly 2 and the limit is exactly 2: the comparison must be < to match "strictly shorter". If the statement says "at most", change it to <=; this is the one place the problem text decides the code.

The skeleton is reusable: whenever every query is a threshold on the same graph and you can answer it by "union everything below the threshold", sort queries by threshold and sweep once. It shows up as offline connectivity, and it is the same trick as sorting events in a sweep line.

Critical and pseudo-critical edges

Ties make the MST non-unique, so a sharper question becomes meaningful: which edges must be in every MST, and which are in some MST? Call an edge critical if it is in every MST, pseudo-critical if it is in some MSTs but not all, and neither if it is in none. The two tests fall straight out of the definitions, with a fresh Kruskal run each:

• Critical: build the MST while forbidding the edge. If the total goes up (or the graph disconnects), the edge was irreplaceable.
• In some MST: build the MST after forcing the edge in first. If the total still equals the unconstrained minimum, there is an MST that contains it.

// O(E² α(V)): the sort happens once, each of the 2E runs is a linear sweep. Assumes no self-loops.
function findCriticalAndPseudoCriticalEdges(n, edges) {
  const order = edges.map(([u, v, w], i) => [u, v, w, i]).sort((a, b) => a[2] - b[2]); // carry the original index

  function weightOfTree(skip, force) {
    const dsu = new DSU(n);
    let cost = 0, used = 0;
    if (force !== -1) {
      const [u, v, w] = edges[force];
      dsu.union(u, v);
      cost += w;
      used++;
    }
    for (const [u, v, w, i] of order) {
      if (i === skip) continue;
      if (dsu.union(u, v)) { cost += w; used++; }
    }
    return used === n - 1 ? cost : Infinity; // disconnected without this edge
  }

  const best = weightOfTree(-1, -1);
  const critical = [], pseudo = [];
  for (let i = 0; i < edges.length; i++) {
    if (weightOfTree(i, -1) > best) critical.push(i);        // check critical FIRST
    else if (weightOfTree(-1, i) === best) pseudo.push(i);   // in some MST but not in all
  }
  return [critical, pseudo];
}

Dry run: n = 5, edges 0: (0,1,1), 1: (1,2,1), 2: (2,3,2), 3: (0,3,2), 4: (0,4,3), 5: (3,4,3), 6: (1,4,6)

The unconstrained MST weighs 7. Running both tests on every edge:

The answer is [[0, 1], [2, 3, 4, 5]]. Edges 2 and 3 are interchangeable: they both close the cycle 0–1–2–3 and an MST needs one of them, so neither is critical. Edges 4 and 5 are interchangeable the same way. Edge 6 is the heaviest edge on a cycle, so the cycle property says it is never needed, and forcing it costs 3 more.

There is a faster solution that groups equal-weight edges and looks for bridges inside each group, but when the edge count is a few hundred the 2E-runs version above is the one to write: each piece is a function you already have, and the two definitions are the whole proof.

Second-best MST: one swap away

The second-best spanning tree is the cheapest tree that is not the MST itself (it may weigh the same, if the MST was not unique). The natural worry is that it could differ from the MST in many edges, so finding it would mean searching a huge space. It never has to: some second-best tree differs from the MST by exactly one edge.

The argument uses the exchange property of spanning trees. Let T be an MST and T′ a cheapest tree other than T. For any edge e that is in T′ but not in T, there is an edge f in T but not in T′ such that both T − f + e and T′ − e + f are spanning trees. Their weights add up to w(T) + w(T′), the same as the originals. T − f + e is a tree other than T, so w(T − f + e) ≥ w(T′). That forces w(T′ − e + f) ≤ w(T), and since T is minimum it equals w(T). So w(T − f + e) = w(T′): the one-swap tree is just as cheap as T′. Therefore it is enough to try every single swap.

Which swaps are legal? Add a non-tree edge e = (u, v) to T and you create one cycle, the tree path from u to v plus e. You must delete an edge on that cycle to get a tree again, and the best choice is the heaviest tree edge on the path. So:

second best = w(T) + min over non-tree edges e of ( w(e) − heaviest edge on the tree path between e's endpoints )

// O(E log E + E·V): one DFS per non-tree edge. Returns null if the graph is disconnected,
// Infinity if the graph is already a tree (no swap exists).
function secondBestMSTWeight(n, edges) {
  const order = edges.map(([u, v, w], i) => [u, v, w, i]).sort((a, b) => a[2] - b[2]);
  const dsu = new DSU(n);
  const adj = Array.from({ length: n }, () => []);
  const inTree = new Array(edges.length).fill(false);
  let total = 0, used = 0;

  for (const [u, v, w, i] of order) {
    if (dsu.union(u, v)) {
      inTree[i] = true;
      adj[u].push([v, w]); // keep the tree itself, to walk paths on it
      adj[v].push([u, w]);
      total += w;
      used++;
    }
  }
  if (used !== n - 1) return null;

  function heaviestOnPath(from, to) {
    const stack = [[from, -1, 0]]; // [node, parent, heaviest edge so far]; iterative, so a path graph cannot overflow the call stack
    while (stack.length > 0) {
      const [node, parent, heaviest] = stack.pop();
      if (node === to) return heaviest;
      for (const [next, w] of adj[node]) {
        if (next !== parent) stack.push([next, node, Math.max(heaviest, w)]);
      }
    }
    return -Infinity;
  }

  let best = Infinity;
  for (let i = 0; i < edges.length; i++) {
    if (inTree[i]) continue;
    const [u, v, w] = edges[i];
    best = Math.min(best, total + w - heaviestOnPath(u, v)); // swap e in, the path's heaviest edge out
  }
  return best;
}

Dry run: n = 4, edges (0,1,1), (1,2,2), (0,2,3), (2,3,4), (1,3,6)

A swap candidate can tie with the MST: if w(e) equals the heaviest edge on its path, the swap costs exactly w(T) and you have found a second MST. That is correct for "cheapest tree other than this one". Some problems ask for the cheapest tree strictly heavier than the MST; then you need the heaviest path edge that is strictly lighter than w(e), so each path query has to track the two largest distinct weights, not one. Read which version is asked before writing the code. For large V, replace the DFS with binary lifting over the tree (store, for each vertex and each power of two, the ancestor and the heaviest edge on the way up) and each query drops to O(log V).

Boruvka's algorithm: every component grabs its cheapest edge

There is a third classic MST algorithm, and it is the one that parallelises. Kruskal needs one global sorted order, and Prim grows one tree at a time. Boruvka works in rounds. At the start of a round, every current component looks at all edges leaving it and picks the cheapest one. By the cut property each of those picks belongs to some MST, so all of them can be accepted at once, merging components. Repeat until one component is left.

Each component merges with at least one other, so the component count at least halves each round and there are at most log₂ V rounds. A round scans the whole edge list once, so the total is O(E log V), the same as Prim with a binary heap, with no heap and no sort.

// O(E log V) time, O(V) extra space. Returns the MST weight, or null if the graph is disconnected.
function boruvkaMST(n, edges) {
  const dsu = new DSU(n);
  const lighter = (a, b) => edges[a][2] < edges[b][2] || (edges[a][2] === edges[b][2] && a < b); // ties broken by edge index
  let components = n, total = 0;

  while (components > 1) {
    const cheapest = new Array(n).fill(-1); // cheapest[root] = index of that component's best outgoing edge
    for (let i = 0; i < edges.length; i++) {
      const ru = dsu.find(edges[i][0]), rv = dsu.find(edges[i][1]);
      if (ru === rv) continue; // inside one component, not outgoing
      if (cheapest[ru] === -1 || lighter(i, cheapest[ru])) cheapest[ru] = i;
      if (cheapest[rv] === -1 || lighter(i, cheapest[rv])) cheapest[rv] = i;
    }

    let merged = false;
    for (let r = 0; r < n; r++) {
      if (cheapest[r] === -1) continue;
      const [u, v, w] = edges[cheapest[r]];
      if (dsu.union(u, v)) { total += w; components--; merged = true; } // two components may have picked the same edge
    }
    if (!merged) return null; // no component had an outgoing edge: disconnected
  }
  return total;
}

Dry run: 6 vertices, edges 0–1 (1), 2–3 (1), 4–5 (1), 1–2 (5), 3–4 (6), 0–5 (9)

Six components became three and then one, and the total 1 + 1 + 1 + 5 + 6 = 14 matches Kruskal. The line that checks dsu.union before counting is not optional: two components often pick the same edge, as above, and it must be added once.

You will rarely be asked to write Boruvka in an interview. It is worth one sentence as an answer to "is there another way?": each round every component picks its cheapest outgoing edge independently, so rounds map well onto parallel or distributed systems, and the idea of "cheapest outgoing edge per component" is a building block in faster MST algorithms.

Recognizing it in an unseen problem

• "Connect all," "minimum cost to link every," "cheapest network/wiring/roads," "keep everything reachable" — total cost over the whole structure, not a route between two nodes
• The graph is undirected and weighted. MST is undefined on a directed graph — that's the arborescence / Chu-Liu-Edmonds problem, and no interviewer expects it
• Brute force would enumerate spanning trees — Cayley's formula says a complete graph on n vertices has nⁿ⁻² of them, so exhaustive search is hopeless and greedy is the whole point
• Distinguish from Dijkstra: if a source vertex is named, or the answer is "distance from A to B," it's shortest paths, not MST
• Distinguish from plain union-find connectivity: if weights are ignored and the question is just "are these connected / how many components," you need the DSU but not the sort
• Per-node costs alongside per-edge costs → add a virtual node and turn the node cost into an edge cost
• Complete/implicit graph on ≥ ~1000 points → O(V²) Prim; explicit sparse edge list → Kruskal
• "Minimise the largest edge on a path," "minimum effort," "smallest limit so that A and B connect" → minimax path: the MST path is optimal, so sweep Kruskal until the endpoints join
• Many queries of the form "connected using only edges below this limit?" → sort the queries by limit as well and answer them in one sweep of union-find
• "Which edges are in every / in some / in no minimum spanning tree" → rerun Kruskal once per edge, skipping it and forcing it
• "Second-cheapest spanning tree," "cost of the best tree that differs from the MST" → one edge swap: add a non-tree edge, remove the heaviest edge on the cycle it closes
• "Maximise the total" or "widest path" on a connectivity problem → negate the weights, or sort descending