#### Depth-First Search(DFS)

In DFS, we begin at some node and goes down a path until it reaches a node that has no children. Any time DFS runs out of moves, it backtracks and expands a sibling of the node. If the node had no siblings, then DFS looks for sibling of the grandparent and so on.

• No matter how deep the current node is, DFS will always go deeper if it has a child.
• DFS will fail to terminate if there is an infinite path. In other words, DFS is not optimal for most problems.

Same as DFS, except nodes of depth equal to a fixed maximum (say M) are not expanded.

• M-Limited DFS will find a solution if a solution exists at depth M or less.
• If a solution exists at a depth greater than M then it won’t be able to find the solution.

#### Iterative Deepening

Performs depth-limited DFS repeatedly with an increasing depth limit until a solution is found.

• Never end up exploring infinite dead-end paths, as length of each path is capped by some length at each step.
• Find shortest possible path to the destination node.
• Run in O(b^d) time but only uses O(d) space.