7.4 Depth First Search and Breadth First Search

• An important way of traversing all vertices of a digraph, with applications in many problems.
• Let L[v] be the adjacency list for vertex v. To do a depth first search of all vertices emanating from v, we have the following recursive scheme:
  
  void dfs (vertex v)

  {

  vertex w;

  mark v as visited;

  for each vertex w $\in$ L[v]

  dfs(w)

  }
  

  
  

    

  Figure 7.10: Depth first search of a digraph

  
  
  

  
  

• To do a dfs on the entire digraph, we first unmark all vertices and do a dfs on all unmarked vertices:
  
  {

  for v $\in$ V

  mark v as unvisited;

  for v $\in$ V

  if (v is unvisited)

  dfs(v);

  }
  
  

Example: See Figure 7.10.

DFS Arcs:

• Tree Arcs: a $\rightarrow$ b, N(a) < N(b) leading to unvisited vertices
• Non-Tree Arcs:
  • back arcs: a $\rightarrow$ b, N(a) $\geq$ N(b), b is an ancestor
  • forward arcs: a $\rightarrow$ b, N(a) < N(b), b is a proper descendant
  • cross arcs: a $\rightarrow$ b. Neither ancestor nor descendant