The muddy city problem asks which damaged or missing roads to repair or build so every location connects, while minimizing total cost. Model locations as vertices and roads as weighted edges; the solution is a minimum spanning tree (MST): a connected, cycle-free subgraph containing every vertex with the smallest possible edge-weight sum. section 4.2
Kruskal’s algorithm solves the problem by:
- Starting with every vertex and no edges. section 4.2
- Sorting roads from lowest to highest weight. section 4.2
- Adding the next road only when it does not create a cycle, then returning the resulting tree. section 4.2
Practical graph implementation
A NetworkX graph can represent locations and weighted roads, compute the MST with Kruskal, and highlight selected edges. The same approach is applied to a road network around the University of Toronto, using OSMnx road data and edge lengths as weights. section 4.2
Algorithm 4.1 Kruskal’s algorithm
Input: Graph G = (V, E) with each edge e ∈ E having a weight w(e)
Output: A minimum spanning tree T
Create a new graph T:= ∅ with the same vertices as G, but with no edges.
Define a list S containing all the edges in the graph G
Sort the edges list S in ascending order of their weights.
For each edge e in the sorted list:
If adding edge e to T does not form a cycle:
Add this edge to T.
Else:
Skip this edge and move to the next edge in the list.
Continue this process until all the edges are processed.
Return T as the minimum spanning tree of graph G.
Follow the stepwise Kruskal procedure for sorting edges, rejecting cycles, and constructing the minimum spanning tree. section 4.2
