Micro-questions over the MST module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The problem
1. What is a spanning tree?
Answer
A tree touching every vertex, using edges. A barebones highway map connecting all cities.
2. What is a minimum spanning tree?
Answer
The spanning tree with the smallest total edge weight. The cheapest possible highway map.
3. Give the motivating illustration.
Answer
Laying fibre-optic cable between cities. Connecting every pair directly wastes millions in redundant wire; an MST finds the cheapest layout where everyone can still reach everyone, with no closed loops.
4. Name three production applications.
Answer
Telecommunications and utilities (water pipes, electrical grids, cabling); single-linkage hierarchical clustering in ML; road system construction with minimal asphalt.
5. Why does an MST have no cycles?
Answer
A cycle means one edge is redundant — everything is still connected without it — so dropping the heaviest edge of any cycle gives a cheaper connected graph. A minimum-weight solution therefore cannot contain one.
B. The cut property
6. State the cut property.
Answer
The cheapest edge crossing any boundary split belongs in the MST. Greedily choosing the cheapest bridge across a river.
7. Why does it hold?
Answer
Any spanning tree must cross the cut somewhere. If it crosses by a more expensive edge, swap that edge for the cheapest crossing one — still spanning, still connected, and strictly cheaper. So the minimum must use the cheapest crossing edge.
8. What do both classic algorithms have in common?
Answer
Both are greedy, and both are correct for the same reason: the cut property. They differ only in which cut they apply it to.
C. Kruskal’s algorithm
9. State Kruskal’s strategy.
Answer
Sort all edges globally by weight, then greedily add the cheapest edge unless both endpoints are already connected — which would create a cycle.
10. What two structures does it need?
Answer
A sorted edge array and union-find.
11. How does union-find detect a cycle?
Answer
union(u, v) returns True only if u and v were not already connected. Returning False means the edge would close a cycle, so you skip it.
12. When can you stop early?
Answer
Once edges_used == V - 1. The tree is complete and the remaining edges cannot improve it.
13. How do you detect a disconnected graph?
Answer
You run out of edges with edges_used < V - 1. No spanning tree exists.
14. What is Kruskal’s time complexity, and what dominates?
Answer
— the sort dominates; the union-find operations are effectively each.
15. Which graph representation does Kruskal want?
Answer
An edge list. It never asks for a vertex’s neighbours, so an adjacency list buys it nothing.
D. Prim’s algorithm
16. State Prim’s strategy.
Answer
Start from any vertex. Use a min-heap to repeatedly attach the cheapest edge connecting an unvisited vertex to the growing tree.
17. Give the physical metaphor.
Answer
Expanding an electrical grid outward from a power station — one connected blob that grows.
18. What two structures does it need?
Answer
A min-heap and a visited set.
19. Why does it need a stale entry check?
Answer
The same vertex can be pushed by several tree vertices at different weights. On pop, if u in visited: continue discards the outdated ones — exactly as in Dijkstra.
20. What is Prim’s time complexity?
Answer
with a binary heap.
21. What does the starting vertex affect?
Answer
Nothing about the total cost. It may change which MST you get when weights tie, but not the weight.
E. Prim’s vs Dijkstra
22. The two algorithms look almost identical. What is the one difference?
Answer
What you push. Dijkstra pushes dist[u] + weight — cumulative distance from the source. Prim pushes weight alone — the cost of this one edge into the tree.
23. Why does that one change produce a completely different object?
Answer
Dijkstra minimises distance from a source to each vertex; Prim minimises the total weight of edges used to connect everything. Different objective, same skeleton.
F. Choosing
24. Compare Kruskal and Prim across four rows.
Answer
| Kruskal | Prim | |
|---|---|---|
| Approach | edges globally | grows one tree from a root |
| Structures | union-find + sort | min-heap + visited set |
| Time | ||
| Best for | sparse () | dense () |
25. Why does Kruskal suit sparse graphs?
Answer
Its cost is dominated by sorting edges, so few edges means little work. On a dense graph you sort edges and most of them get rejected.
26. Space complexity of either?
Answer
— the union-find parent array, the heap, and the adjacency or edge structures.
27. What if the graph is already given as an edge list from a file?
Answer
Kruskal, without hesitation — it consumes that representation directly, while Prim would need you to build an adjacency structure first.
G. Traps
28. Does MST apply to directed graphs?
Answer
No. Directed graphs need a minimum arborescence, via Edmonds’ algorithm — a completely different and more complex construction.
29. Does an MST contain the shortest path between two vertices?
Answer
Not necessarily. An MST minimises total global edge weight, not individual path lengths. A path between two nodes in the MST can be far longer than their shortest path in the original graph. Use Dijkstra for shortest paths.
30. What happens on a disconnected graph?
Answer
No spanning tree exists — you cannot place edges. What you get instead is a minimum spanning forest, one tree per component.
31. Is the MST unique?
Answer
Only if all edge weights are distinct. With ties, several MSTs of equal total weight can exist — which is why tests should assert the total cost, not a specific edge set.
32. Summarise MST in one sentence.
Answer
Connect everything as cheaply as possible with no redundancy — greedily, by the cut property, either sorting all edges (Kruskal) or growing one blob (Prim).
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Minimum Spanning Tree — the module
- Union-Find — what makes Kruskal work
- Dijkstra — Question Bank — the near-identical algorithm with a different push
Software engineering
Infrastructure & security
Computer science
Hardware & engineering