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.

Figure 5.27. A minimum spanning tree

The edges of a minimum spanning tree are drawn thick. The overall weight of this tree is 65.

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 done 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).