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
KruskalPrim
Approachedges globallygrows one tree from a root
Structuresunion-find + sortmin-heap + visited set
Time
Best forsparse ()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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms