LEDA Guide: DFS and BFS Example

> LEDA Guide > Graph Algorithms > Basic Graph Algorithms > DFS and BFS > Example

Example Depth First Seach and Breadth First Search

The following example shows how to use the LEDA functions for DFS and BFS.

The program first creates a graph G with seven nodes and five edges.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/basic_graph_alg.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();node n5=G.new_node();
  node n6=G.new_node();

  G.new_edge(n5,n0);G.new_edge(n5,n1);
  G.new_edge(n5,n2);G.new_edge(n1,n3);
  G.new_edge(n4,n6);

The first variant of DFS uses a

node_array<bool> 
      reached

to label the nodes that are reached from the starting node n5 with true. This variant returns the list of reached nodes. The nodes appear in this list in the order they were visited. Our program outputs the list for G and n5.

  //first variant of DFS
  node_array<bool> reached(G,false); 
             //DFS expects value false for all nodes
  list<node> LN1=DFS(G,n5,reached);
  
  node v;
  std::cout << "LN1:";forall(v,LN1) G.print_node(v);
  std::cout << std::endl << std::endl; //prints LN1:[5][0][1][3][2]

The second variant of DFS, called DFS_NUM(), numbers the nodes of G in two different ways. The

node_array<int> 
      dfsnum

is a numbering with respect to the calling time and

node_array<int> 
      compnum

is a numbering with respect to the completion time of the recursive calls. DFS_NUM() returns a DFS forest, that is, a list of tree edges that lead to reachable nodes. We print

dfsnum, 
      compnum

and the list of tree edges.

  //second variant of DFS
  node_array<int> dfsnum(G);
  node_array<int> compnum(G);
  list<edge> LE=DFS_NUM(G,dfsnum,compnum);
    //start nodes for BFS are chosen in order of creation
	   
  forall_nodes(v,G) {
    G.print_node(v);
    std::cout << " dfsnum[v]=" << dfsnum[v];
    std::cout << " compnum[v]=" << compnum[v] << std::endl;
  }

  edge e;
  std::cout << "LE: ";forall(e,LE) G.print_edge(e);
  std::cout << std::endl << std::endl; //prints LE: [1]---->[3][4]---->[6]

The first variant of BFS uses a node_array<int> dist1 for the result of a Breadth First Search on G starting at node n5. After the call of BFS() we have dist[v]=-1 for nodes v not reachable from n5. For the other nodes v dist[v] is the distance from

n5

to v in G. The list of visited nodes is returned. The nodes appear in this list in the order they were visited. Our program outputs the dist values of all nodes and the list of visited nodes for G and n5.

  //first variant of BFS
  node_array<int> dist1(G,-1);   
                     //BFS expects value -1 for all nodes
  list<node> LN2=BFS(G,n5,dist1);

  forall_nodes(v,G) {
    G.print_node(v);
    std::cout << " dist1[v]=" << dist1[v] << std::endl;
  }  //dist1[v]=-1 for [4],[6], dist1[v]=0 for [5], 
     //dist1[v]=1 for [0],[1],[2], dist1[v]=2 for [3]

  std::cout << "LN2: ";
  forall(v,LN2) G.print_node(v);
  std::cout << std::endl << std::endl; // prints LN2: [5][0][1][2][3]

The second variant of BFS extends the first variant by a

node_array<edge> 
      pred

that contains for every node v of G the edge that was used by BFS to reach v or nil if v is unreachable from s. pred corresponds to the list of edges returned by DFS_NUM(). We output pred and the list of reached nodes.

  //second variant of BFS
  node_array<int> dist2(G,-1);
                    //BFS expects value -1 for all nodes
  node_array<edge> pred(G);
  list<node> LN3=BFS(G,n5,dist2,pred);

  forall_nodes(v,G) {
    G.print_node(v);
    std::cout << " dist2[v]=" << dist2[v] << " ";
    if (pred[v]!=nil) G.print_edge(pred[v]);
    std::cout << std::endl;
  }  //dist2[v]=dist1[v] for all v-1 for [4],[6]
     //pred[[0]]=[5]---->[0]  pred[[1]]=[5]---->[1]
     //pred[[2]]=[5]---->[2]  pred[[3]]=[1]---->[3]
     //pred[v]=nil for [4],[5],[6]

  std::cout << "LN3: ";
  forall(v,LN3) G.print_node(v);
  std::cout << std::endl << std::endl; // prints LN3: [5][0][1][2][3]

  return 0;
}

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

Example Depth First Seach and Breadth First Search

See also: