*Learning objectives*

Algorithms from `min_span.h` |

Spanning trees |

Minimum spanning trees |

In a city, intersections (nodes) are connected by streets
(edges). Each street has a certain length, see Figure 5.27. Now an electricity network is
to be built that provides all intersections with
electricity. Cables may be laid only under streets that already
exist. Since tearing open the streets, laying the cables
underneath, recovering everything with concrete, and the cables
themselves are expensive, the question is how to connect all
intersections with a network that is as short as possible. This
means that a *minimum* electricity network is
to be *spanned* that provides all intersection
points with electricity.

Such a net is always a tree that is a subgraph of the street
graph and that comprises all nodes of the graph. Such a tree is
called a *spanning
tree*. A spanning tree that minimizes the sum of the
edge weights is called a *minimum spanning
tree*.

Here it is assumed that the underlying graph is
connected. This does not necessarily have to hold, though. In a graph
that is not connected the definition can be expanded to a *minimum spanning forest*.

LEDA offers some functions for computing minimum
spanning trees. They all are declared in the header file
* min_span.h*. An
example is the function

list<edge> MIN_SPANNING_TREE(graph G&, edge_array<int>& weight);

which returns the edges of a minimum spanning tree (or a forest) of
`G`

. The edge weights are passed to it in the edge
array `weight`

.

To clarify the usage of this function, we list the program that has been used to create Figure 5.27. It allows the user to edit a graph in a GraphWin; pressing makes visible a minimum spanning tree and its overall weight.

#include <LEDA/min_span.h> #include <LEDA/graph.h> #include <LEDA/edge_array.h> #include <LEDA/graphwin.h> #include <LEDA/list.h> #include <LEDA/string.h> using leda::GRAPH; using leda::edge_array; using leda::edge; using leda::node; using leda::GraphWin; using leda::window; using leda::list; using leda::string; int main() { GRAPH<int,int> G; GraphWin gw(G, 500, 500, "Minimum Spanning Tree"); gw.set_edge_direction(leda::undirected_edge); gw.set_edge_label_type(leda::data_label); gw.set_flush(false); gw.display(window::center,window::center); while(gw.edit()) { edge_array<int> weight(G); edge e; forall_edges(e,G) weight[e] = G.inf(e); list<edge> L = MIN_SPANNING_TREE(G, weight); // minimum spanning tree may have changed // so reset drawing to initial values gw.set_edge_width(1); gw.set_edge_color(leda::black); gw.set_width(L, 4); gw.set_color(L, leda::red); int weight_of_tree = 0 ; forall(e, L) weight_of_tree += weight[e]; gw.message("The weight of this mimimum spanning tree is " + string("%d", weight_of_tree) + ". Click <done>."); gw.wait(); gw.del_message(); gw.redraw(); } }

In contrast to `MIN_SPANNING_TREE()`

, the function

list<edge> SPANNING_TREE(graph& G);

computes merely a spanning tree, that is, it does not take edge weights into consideration (or considers them to be 0).

`MIN_SPANNING_TREE()`

takes time
O(m·log(n)); in contrast, `SPANNING_TREE()`

takes only time
O(n+m).

Further information about these functions can be found on
the manual page of
`min_span.h`

.