Example Lists of Nodes

The following example implements a breadth first search for a graph using a node_list.

In the main() function a graph with seven nodes and six edges is generated. Then a node_list Q is defined and used in the call of function bfs(). Finally the size of Q, that is, the number of nodes examined by bfs(), and the nodes contained in Q are printed.

The function bfs() first appends the starting node to Q and then examines nodes of G in a while-loop. It examines all outgoing edges of the current node v and checks whether the target node w is a member of Q. If w is not contained in Q, it is appended and size is incremented.

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

using namespace leda;

int bfs(node s,const graph& G,node_list& Q) 
{ 
  int size=1;
  Q.append(s);
  
  node v=Q.head();
  while (v!=nil) {
    edge e;  forall_adj_edges(e,v) { 
      node w=G.target(e);
      if (!Q.member(w)) {Q.append(w);size++;}
    }

    v=Q.succ(v);
  }

  return size;
}

int main()
{
  graph G;

  node v[7];
  for (int i=0;i<7;i++) v[i]=G.new_node();

  G.new_edge(v[0],v[1]);G.new_edge(v[0],v[2]);
  G.new_edge(v[0],v[3]);G.new_edge(v[1],v[4]);
  G.new_edge(v[1],v[5]);G.new_edge(v[6],v[5]);

  node_list Q;
  int size=bfs(G.first_node(),G,Q);

  cout << "Q contains " << size << " nodes\n";
  node w;  forall(w,Q) G.print_node(w);
  std::cout << std::endl;

  return 0;
}

See also:

Breadth First Search

Manual Entries:

Manual Page Lists of Nodes

Iteration