LEDA Guide: Example Spanning Trees and Minimum Spanning Trees

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Spanning Trees and Minimum Spanning Trees > Example

Example of How to Use `SPANNING_TREE()` and `MIN_SPANNING_TREE()`

The following program shows how the functions SPANNING_TREE() and MIN_SPANNING_TREE()can be used to compute a spanning tree and a minimum spanning tree in a graph.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

We first create a graph G with five nodes and nine edges and call SPANNING_TREE() for G. SPANNING_TREE() returns the list of edges of the spanning tree. After that we define edge_array<int> cost to store the costs on the edges of G and call MIN_SPANNING_TREE() for G and cost. The result is the list of edges in the minimum spanning tree.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/min_span.h>

using namespace leda;

int main()
{
  graph G; 

  node n0=G.new_node(); node n1=G.new_node();
  node n2=G.new_node(); node n3=G.new_node();
  node n4=G.new_node();
  
  edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n2);
  edge e2=G.new_edge(n0,n4); edge e3=G.new_edge(n1,n2);
  edge e4=G.new_edge(n1,n3); edge e5=G.new_edge(n1,n4);
  edge e6=G.new_edge(n2,n3); edge e7=G.new_edge(n2,n4);
  edge e8=G.new_edge(n3,n4);

  list<edge> tree_edges=SPANNING_TREE(G);

  std::cout << "Spanning tree: ";
  edge e; forall(e,tree_edges) G.print_edge(e);
  std::cout << std::endl;

  edge_array<int> cost(G);
  cost[e0]=3; cost[e1]=1; cost[e2]=4; cost[e3]=1;
  cost[e4]=1; cost[e5]=1; cost[e6]=1; cost[e7]=1;
  cost[e8]=1;

  list<edge> min_tree_edges=MIN_SPANNING_TREE(G,cost);

  std::cout << "Minimum spanning tree: ";
  forall(e,min_tree_edges) G.print_edge(e);
  std::cout << std::endl;

  return 0;
}

Example of How to Use SPANNING_TREE() and MIN_SPANNING_TREE()

See also:

Example of How to Use `SPANNING_TREE()` and `MIN_SPANNING_TREE()`