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

2026-11-09 · 13 min · Ramesh

Algorithms - Graphs

Undirected Graphs Some problems Path Shortest path Cycle Ehler tour: A cycle that uses each edge excatly once. Hamilton tour: A cycle that uses each vertex exactly once classical NP-complete problem. Connectivity MST: Biconnectivity: A vertex whose removal disconnects the graph Planarity Graph isomorphism: Are two graphs identical? No one knows so far. A lonstanding open problem Representations Real-world graphs tend to be sparse (huge number of vertices, small average vertex degree). ...

2024-03-01 · 12 min · Ramesh