Kruskal's algorithm builds a minimum spanning tree (MST) for an undirected, connected, weighted graph. It sorts edges from smallest to largest and repeatedly adds the next edge unless that edge creates a cycle. The result connects every vertex without loops while minimizing the total edge weight. section 4.2 section 4.5
The muddy city problem
Treat road lengths as edge weights and repair only the roads needed to connect every location. Choose E-H with length 1 first; then select the length-2 edges that do not create cycles. Among length-3 edges, reject C-F and F-J because they close cycles, while accepting A-D, D-E, and G-I. Reject A-E at length 4 for the same reason, then finish with G-H. Arbitrary choices are possible when edges have equal weights. section 4.2
A Python implementation can use NetworkX to test connectivity and cycles, then visualize the selected MST by highlighting its edges. The same approach scales to a road network: an OSMnx graph of the University of Toronto area is converted to an undirected graph, its edges are sorted by length, and the MST edges are highlighted. section 4.2
