A spanning tree is a cycle-free subgraph of an undirected graph that contains every vertex and connects them with the minimum number of edges. It models a connected road or network plan without redundant loops; when edges carry costs, the minimum spanning tree minimizes their total weight. section 4.2
Check these conditions:
- Include every vertex from the original graph. section 4.2
- Keep the subgraph connected, with no circuits or self-loops. section 4.2
- For an MST, compare the summed edge weights and retain a lowest-weight spanning tree. section 4.2
Repairing a muddy city
Treat damaged roads as weighted edges and towns as vertices. Kruskal’s algorithm sorts roads by weight, adds each edge that does not create a cycle, and returns the resulting MST. 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.
Use the pseudocode to follow Kruskal’s edge-selection process. section 4.2
