### 5.3.6. Minimum spanning trees

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.

Filename: MinimumSpanningTree.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#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).

#### Running times and further information

`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`.