(* 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 ;;