About
Minimum spanning forest
Articles Related
Definition
- input: a graph G, and an assignment of real-number weights to the edges of G.
- output: a minimum-weight set S of edges that is spanning and a Tree - Forest (Set of Tree).
Application
Application: Design hot-water delivery network for the university campus:
- Network must achieve same connectivity as input graph.
- An edge represents a possible pipe.
- Weight of edge is cost of installing the pipe.
- Goal: minimize total cost.
Grow
def Grow(G)
S := 0;
consider the edges in increasing order # Increasing order: 2, 3, 4, 5, 6, 7, 8, 9.
for each edge e:
if e’s endpoints are not yet connected
add e to S.
Shrink
def Shrink(G)
S = {all edges} consider the edges in order, from highest-weight to lowest-weight # Decreasing order: 9, 8, 7, 6, 5, 4, 3, 2.
for each edge e:
if every pair of nodes are connected via S -{e}:
remove e from S.