(* Depth First Search *)

exception No_vertex;;

let rec unvisitedNeighbor v edges visited =
   match edges with
      [] -> raise No_vertex
    | ((v1,v2)::t) ->
      if (v1 <> v || List.mem v2 visited) then
         (unvisitedNeighbor v t visited)
      else
         v2
;;

(* Depth First Search. Returns unit.
   Prints list of visited nodes, which is also in the list referenced by visitedref *)
let rec dfs v edges visitedref =
   visitedref :=
      (if List.mem v !visitedref then
         !visitedref
      else
         (print_int v; v::!visitedref));

   try
      let u = (unvisitedNeighbor v edges !visitedref) in
      dfs u edges visitedref;
      dfs v edges visitedref
   with No_vertex -> ()
;;

let c4 = [(0,1);(1,2);(2,3);(3,0)];;

dfs 0 c4 (ref[]);;
print_newline ();;

dfs 2 c4 (ref[]);;
print_newline ();;

let tree = [(0,1);(0,2);(0,3);(1,4);(1,5);(3,6);(6,7)];;

dfs 0 tree (ref[]);;
print_newline ();;

let other = [(0,1);(0,2);(1,3);(1,4);(2,5);(2,6);
             (3,7);(4,7);(5,8);(6,8);(7,9);(8,9)];;

dfs 0 other (ref[]);;
print_newline ();;

(* Returns the list of visited nodes. *)
let dfs2 v edges =
   let x = ref [] in
   dfs v edges x;
   !x
;;