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

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 |
|---|---|---|---|---|
|
| accept |
| 1 |
|
| accept |
| 3 |
|
| accept |
| 5 |
|
| accept |
| 8 |
| both in | reject, cycle |
| 8 |
|
| accept, then stop |
| 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.

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:
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.

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 |
|
|
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-1accepted edges? A connected acyclic graph onVvertices hasV-1edges.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.
Keep learning
Kruskal's Algorithm and MST Explained: A Step-by-Step Worked Example
Learn what an MST is, how DSU makes Kruskal's cycle decisions, and how a seven-vertex graph reaches six selected edges with total weight 14.
MST and Kruskal's Algorithm MCQs: 12 Solved Questions with Explanations
Test your MST fundamentals across 12 solved MCQs. Each answer explains the shortcut, trap, or Kruskal trace you need for exam questions.
MST and Prim's Algorithm Interview Questions: Model Answers and Worked Traces
Build an interview-ready understanding of minimum spanning trees and Prim's algorithm through an exact trace, correctness proof, Kruskal comparison and edge-case checks.
Prim's Algorithm and Minimum Spanning Tree: Worked Example, Complexity and Exam Traps
Learn what makes Prim's greedy choice safe, trace every key update on a six-vertex graph, and avoid the mistakes that derail MST questions.





