Minimum Spanning Trees in Java Interviews: Kruskal vs Prim, and When the Interviewer Asks for the Second-Best
The setup is four cities and six possible roads, each with a cost. Connect all four cities so that every city is reachable from every other, and spend as little as possible. The answer is always exactly n-1 roads — fewer can’t connect everything, more must contain a cycle, and a cycle means you’re paying for a road you don’t need. A minimum spanning tree is the cheapest such set. ...