- 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 L[v]dfs(w)

}

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

{**for***v**V*mark

*v*as unvisited;**for***v**V***if**(*v*is unvisited)dfs(

*v*);}

**DFS Arcs:**

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

- back
arcs: