Kruskal's Algorithm Interview Questions: MST Traces, DSU and Model Answers

Trace Kruskal's algorithm on a six-vertex graph, then rehearse model answers on DSU, correctness, complexity, ties, negative weights and disconnected inputs.

KnowledgeGate Team

Exam prep & CS education

Updated 14 Nov 20266 min read
Kruskal's Algorithm Interview Questions: MST Traces, DSU and Model Answers

Kruskal's algorithm is easy to state and easy to misapply: sorting edges is only half the answer, and DSU must reject edges that close a cycle. A six-vertex example gives the accepted edges, running cost and proof ideas you can explain in an interview, followed by code structure and edge-case checks.

1. What is an MST, and when does one exist?

For a connected, undirected, weighted graph, a spanning tree connects all V vertices without a cycle. It therefore has exactly V-1 edges. A minimum spanning tree, or MST, is the spanning tree with the smallest total edge weight. If the graph is disconnected, one spanning tree cannot cover every vertex, although Kruskal can return a minimum spanning forest.

Do not confuse this objective with shortest paths. In the triangle A-B=2, B-C=2, A-C=3, the MST chooses A-B and B-C, with total weight 2+2=4. However, the shortest route from A to C is the direct edge with weight 3, not the MST path with weight 4. An MST minimises the total tree weight, not distance from one source.

The standard MST definition also assumes undirected edges. A directed minimum arborescence is a different problem.

2. How does Kruskal's algorithm work? Trace all six vertices

The interview-ready procedure is simple: sort edges in nondecreasing weight order, scan from lightest to heaviest, and accept an edge only when its endpoints are in different components. Union those components, then stop after accepting V-1 edges. Equal-weight edges may use a stable tie-break for reproducible output, but correctness does not depend on that presentation choice.

Use vertices {A,B,C,D,E,F} and the sorted edges B-C=1, A-C=2, D-E=2, E-F=3, A-B=4, B-D=5, D-F=6, B-E=7, C-D=8, C-E=10.

The roots column below shows the components relevant to each decision. The trace stops at B-D; heavier edges remain unscanned because the MST is already complete.

edge

roots/components before

decision

components after

running total

B-C=1

{B},{C}

accept

{BC},{A},{D},{E},{F}

1

A-C=2

{A},{BC}

accept

{ABC},{D},{E},{F}

3

D-E=2

{D},{E}

accept

{ABC},{DE},{F}

5

E-F=3

{DE},{F}

accept

{ABC},{DEF}

8

A-B=4

both in {ABC}

reject, cycle

{ABC},{DEF}

8

B-D=5

{ABC},{DEF}

accept, then stop

{ABCDEF}

13

The accepted set is {B-C,A-C,D-E,E-F,B-D}. Five edges have been accepted because V-1=6-1=5, and the arithmetic check is 1+2+2+3+5=13.

Six-vertex weighted graph highlighting five orange MST edges, rejecting A-B with a red X, and showing five accepted edges with total cost 13.

3. Why is Kruskal's greedy choice correct? Give a cut answer and a cycle answer

The cut property says a lightest edge crossing a cut is safe for some MST. The cycle property says the unique heaviest edge on a cycle cannot belong to an MST. The trace demonstrates both answers.

Use the final merge for the cut-property answer. Immediately before B-D=5, the components are {A,B,C} and {D,E,F}. The crossing edges are B-D=5, B-E=7, C-D=8, and C-E=10. Since B-D is the lightest crossing edge, accepting it is safe for some MST. If a candidate optimum used a heavier crossing edge, replacing that edge with B-D would reconnect the cut without increasing the cost.

For the cycle-property answer, look at A-B=4. Accepted edges A-C=2 and C-B=1 already connect A and B. Adding A-B creates the triangle A-C-B-A, in which weight 4 is the unique heaviest edge. It cannot improve the MST, so Kruskal rejects it.

For a fuller treatment of cuts, cycles, Prim's algorithm, and uniqueness, study Minimum Spanning Tree for GATE: Kruskal and Prim Numericals with Unique-MST Questions.

4. How do you code Kruskal with DSU, and what is its complexity?

Use DSU to represent the current components:

Code
for each vertex v: makeSet(v)
sort edges by (weight, u, v)
for each (u, v, w):
    if find(u) != find(v):
        accepted.append((u, v, w))
        total = total + w
        union(u, v)
        if accepted.size == V-1: break
if accepted.size < V-1: report "no spanning tree"

The (weight,u,v) order only makes ties deterministic. Calling union before comparing the roots would destroy the cycle test. Path compression shortens later find operations, while union by rank or size prevents tall DSU trees.

Initialise every vertex, including an isolated one, before scanning edges. Otherwise, disconnected-input reporting can silently miss a vertex that never occurs in an accepted edge.

Sorting costs O(E log E). All DSU operations together cost O(E alpha(V)) amortised, so sorting dominates. DSU needs O(V) auxiliary space; holding the input edge list needs O(E) space. If edges are already sorted, the scan costs O(E alpha(V)).

After you can explain the pseudocode and bounds, DSA using Java is an optional route for practising graph implementations and complexity explanations.

Seven-panel Kruskal trace showing components merge from six singletons to one set, reject A-B as a cycle, and end with running total 13.

5. What changes under ties, negative weights and disconnected inputs?

In the original graph, A-C=2 and D-E=2 join different component pairs. Either may be processed first, and the final MST remains the same. Repeated weights do not automatically imply multiple MSTs.

Now change only A-B from weight 4 to 2. Two MSTs are possible:

  • {B-C=1,A-C=2,D-E=2,E-F=3,B-D=5}

  • {B-C=1,A-B=2,D-E=2,E-F=3,B-D=5}

Inside the modified triangle, B-C=1 is chosen, while either A-C or A-B attaches A at weight 2. The remaining chosen connectors stay unchanged, so the displayed trees have the same total.

Each contains five edges and costs 1+2+2+3+5=13. The alternative choice inside triangle A-B-C proves non-uniqueness here, but not every tie creates an alternative MST.

Negative weights cause no problem. For P-Q=-3, Q-R=2, P-R=4, Kruskal chooses P-Q and Q-R, giving -3+2=-1. It still compares edge weights and prevents cycles.

For disconnected vertices {X,Y,Z} with only X-Y=1, the result is forest edge {X-Y} with cost 1. Because only one edge was accepted while V-1=2, the function must also report that no spanning tree exists.

6. Kruskal or Prim: which answer fits the representation?

comparison

Kruskal

Prim

growth

forest of components

one tree from a start vertex

main data structure

sorted edges plus DSU

adjacency structure plus priority queue

typical complexity

O(E log E)

O(E log V)

natural input

edge list

adjacency list or matrix

disconnected behaviour

naturally yields a minimum spanning forest

must restart for each component

For V=1000, E=1500 supplied as an edge list, Kruskal is a direct fit. For a dense connected graph supplied as a 500 x 500 adjacency matrix, matrix-based Prim in O(V^2) is reasonable. These are representation-based choices, not fixed rules about which algorithm is always faster.

For the companion Prim interview treatment, see Prim's Algorithm Interview Questions: MST Invariants and Model Answers for the start-vertex growth invariant and priority-queue walk; edge sorting, DSU components and cycle decisions suit an edge-list implementation.

7. Which follow-ups expose memorised answers? Use five checks

  • Why stop at V-1 accepted edges? A connected acyclic graph on V vertices has V-1 edges.

  • Can a self-loop enter an MST? No. Both endpoints share one root, creating a cycle.

  • What if every edge in a connected graph has weight w? Every spanning tree has total (V-1)w.

  • Can DFS replace DSU? Yes, but repeated checks are slower and less clean than amortised DSU.

  • What must the function return? Chosen edges, total cost, and explicit connectivity.

Test one vertex with no edges, returning cost 0; parallel edges X-Y=5 and X-Y=2, selecting weight 2; and self-loop A-A=-4, rejected despite being lightest.

For broader placement preparation, explore Placement Preparation for the wider route.

8. Kruskal interview answer: the 45-second version and next step

Your spoken recap is four lines: sort edges; use DSU to accept only edges joining different components; stop after V-1 accepted edges; justify the choice with the cut property and quote O(E log E) because sorting dominates. In this trace, that means five accepted edges and total cost 13.

For rehearsal, redraw the ten-edge graph, reproduce the decisions, then explain why changing A-B to 2 gives two MSTs of cost 13, without notes. The Interview & Resume Preparation Course is an optional next step for mock-interview practice.