## Introduction

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It is a fundamental algorithm in computer science and has many applications such as finding connected components, topological sorting, and solving puzzles like the maze.

## Implementation

Here is an implementation of DFS in OCaml:

``````type 'a graph = ('a * 'a list) list

let rec explore visited graph node =
if List.mem node visited then visited
else node :: List.fold_left (fun acc n -> explore acc graph n) visited (List.assoc node graph)

let dfs graph start =
List.rev (explore [] graph start)
``````

The `graph` is represented as a list of pairs, where each pair consists of a node and its adjacent nodes. The `explore` function recursively explores the graph by visiting each unvisited node and its adjacent nodes. The `visited` parameter keeps track of the visited nodes to avoid visiting them again. The `dfs` function calls `explore` with an empty `visited` list and the starting node and returns the visited nodes in reverse order.

Here is an example of using the `dfs` function:

``````let graph = [("A", ["B"; "C"; "D"]);
("B", ["E"]);
("C", ["F"]);
("D", []);
("E", []);
("F", ["G"]);
("G", [])]

let visited = dfs graph "A"

let () = List.iter print_endline visited
``````

The output should be:

``````A
B
E
C
F
G
D
``````

## Step-by-step Explanation

1. Start at the given starting node.
2. Mark the node as visited and add it to the visited list.
3. For each adjacent node that is not visited, recursively call `explore` with the visited list and the adjacent node.
4. Return the visited list in reverse order.

## Complexity Analysis

The time complexity of DFS is O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges in the graph. This is because DFS visits each vertex and each edge once. The space complexity is O(|V|), where |V| is the maximum number of vertices in the recursion stack. This is because DFS stores the visited nodes in a list and uses recursion to explore the graph, which creates a stack of function calls.