A minimum spanning tree (MST) connects every vertex in a connected, undirected, weighted graph with no cycles while minimizing the sum of its edge weights. It chooses a cost-effective connected structure rather than preserving every available edge. MST problems belong to informed search, where edge costs guide the search toward an optimal solution. section 4.1 section 4.2
Common MST strategies differ in how they grow or merge tree components:
- Kruskal’s algorithm sorts edges by increasing weight, adds the next edge that does not create a cycle, and continues until the tree is complete. section 4.1 section 4.2
- Jarník-Prim’s algorithm starts at a root and repeatedly adds the lowest-weight edge from the current MST to a non-MST vertex. section 4.1
- Borůvka’s algorithm begins with one tree per vertex, selects the cheapest outgoing edge for each tree, and merges the resulting components; it also handles minimum spanning forests for disconnected graphs. section 4.1
Repairing a muddy city
Treat damaged roads as weighted edges, where weight represents repair or paving cost. Kruskal’s algorithm examines roads from cheapest to most expensive, keeps a road when it connects components without forming a loop, and produces a connected minimum-cost road network. The same workflow can be visualized on a toy graph or applied to a real street network near the University of Toronto. 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 compact Kruskal procedure from graph input through edge sorting, cycle checks, and the returned tree. section 4.2
A practical Python workflow can construct a NetworkX graph, attach weights, compute the MST with Kruskal’s implementation, and highlight selected edges. Real street data can be loaded with OSMnx, converted to an undirected graph, and sorted by road length before computing the tree. section 4.2
