Notes on DFS

The notes from this post build on top of remarks made by David Eppstein.

Depth-first-search, otherwise known as DFS, is a traversal algorithm that aims at exploring a data structure as far down as possible before backtracking. In its counter-part, breadth-first-search traversals, we can define an iterative version using a queue. Enqueuing each successor of a newly visiting node.

I was too under the miss-conception that simply replacing a Queue with a Stack would yield a DFS traversal. However, as pointed out by David, this is not really correct. It works for tree data structures (which was the extent of my thought-exercises) but it produces incorrect traversals over arbitrary data structures.

I was challenged by my advisor to implement the corrected iterative Stacked DFS, as per David’s post, using Sequences to iterate over adjacencies of some node.

let dfs_stack g s =
  let adj = Array.map (fun x -> List.to_seq x) g in

  let visited = ref (Visited.singleton s) in
  let stack = Stack.create () in
  Stack.push s stack;

  Printf.printf "Visiting: %d\n" s;
  while not (Stack.is_empty stack) do
    let hd = Stack.top stack in
    let next = Seq.uncons (Array.get adj hd) in

    match next with
    | Some (w, r) ->
       adj.(hd) <- r;
       if not (Visited.mem w !visited) then begin
         Printf.printf "Visiting: %d\n" w;

         visited := Visited.add w !visited;
         Stack.push w stack;
       end
    | None -> let _ = Stack.pop stack in ()
  done

This is the first correct version shown by David. It is an almost one-to-one copy of the Python code presented. Though we need to manually update the sequence of the rest of adjacencies of the current visting node hd with adj.(hd) <- r, whereas this is internally done in Python when calling next().

let graph x = Array.make x []

let () =
  let g = graph 9 in

  Array.set g 0 [1; 3]      ;
  Array.set g 1 [0; 2; 4]   ;       (*   0 -- 1 -- 2 *)
  Array.set g 2 [1; 5]      ;       (*   |    |    | *)
  Array.set g 3 [0; 4; 6]   ;       (*   |    |    | *)
  Array.set g 4 [1; 3; 5; 7];       (*   3 -- 4 -- 5 *)
  Array.set g 5 [2; 4; 8]   ;       (*   |    |    | *)
  Array.set g 6 [3; 7]      ;       (*   |    |    | *)
  Array.set g 7 [4; 6; 8]   ;       (*   6 -- 7 -- 8 *)
  Array.set g 8 [5; 7]      ;

  dfs_stack g 0;

Using an arbitrary non-tree graph that makes up a grid of 9 nodes, employing over it this new corrected version of an iterative DFS will yield a traversal that is:

0 -> 1 -> 2 -> 5 -> 4 -> 3 -> 6 -> 7 -> 8