Question presented to candidate: "Both Kruskal's and Prim's algorithms find a minimum spanning tree. How does each one work, why are both correct, and which would you pick for a given graph? Please implement both in Python."
What a strong answer should cover:
- The goal: a minimum spanning tree connects all V vertices with V - 1 edges of minimum total weight, for a connected, undirected, weighted graph.
- Kruskal is edge-first: sort all edges, take each one that joins two different components (checked with union-find), O(E log E).
- Prim is vertex-first: grow one tree from a start vertex, always adding the cheapest edge that leaves it, using a min-heap, O(E log V); an O(V²) array version suits dense graphs.
- Why both are correct: the cut property (the cheapest edge across any cut is safe); and the practical differences: sparse vs dense, edge list vs adjacency list, a spanning forest for disconnected graphs (Kruskal) vs one component (Prim).
- Python specifics:
sorted(edges, key=...)for Kruskal,heapq(a min-heap) of(weight, vertex, from)tuples for Prim, and the tie trap: tuples compare element by element, so a non-comparable payload in a tuple raisesTypeErroron equal weights.
Clarifying questions expected:
- "Is the graph connected, and if not, do you want a spanning forest?"
- "How is the graph given: an edge list or an adjacency list? Roughly how many edges per vertex?"
Code / implementation expected: Yes — both in Python: Kruskal with a small union-find, and lazy Prim with heapq.