4.1 Depth first

The pseudocode to perform depth first search is in listing 1.


Listing 1:depthfirstsearch
 
1define sub dfs 
2  by reference G = (V, E) : graph 
3  by reference Visited : set of Vertices 
4  by value x : vertex 
5  if (not (x in Visited)) then 
6    add x to Visited 
7    for each (x, y) in E do 
8      invoke dfs G <> G, Visited <> Visited, y <> x 
9    end for 
10  end if 
11end define sub

No stack is explicitly used because the subroutine is recursive. The set Visited is necessary so we know when to stop in the case of cycles. The initial call should supply an empty set for Visited and a start vertex for x.