In depth-first search, the frontier acts like a last-in first-out stack. The elements are added to the stack one at a time. The one selected and taken off the frontier at any time is the last element that was added.

Example: Consider the tree-shaped graph in Figure. Suppose the start node is the root of the tree (the node at the top) and the nodes are ordered from left to right so that the leftmost neighbor is added to the stack last. In depth-first search, the order in which the nodes are expanded does not depend on the location of the goals

The first sixteen nodes expanded are numbered in order of expansion in Figure. The shaded nodes are the nodes at the ends of the paths on the frontier after the first sixteen steps.

Notice how the first six nodes expanded are all in a single path. The sixth node has no neighbors. Thus, the next node that is expanded is a child of the lowest ancestor of this node that has unexpanded children.

Implementing the frontier as a stack results in paths being pursued in a depth-first manner - searching one path to its completion before trying an alternative path. This method is said to involve backtracking.

The algorithm selects a first alternative at each node, and it backtracks to the next alternative when it has pursued all of the paths from the first selection.

Some paths may be infinite when the graph has cycles or infinitely many nodes, in which case a depth-first search may never stop.

Algorithm:

1. If the initial state is a goal state, quit and return success.

2. Otherwise, loop until success or failure is signaled.

a) Generate a state, say E, and let it be the successor of the initial state. If there is no successor, signal failure.

b) Call Depth-First Search with E as the initial state.

c) If success is returned, signal success. Otherwise continue in this loop.

Performance Evaluation:

Completeness: It is complete, if m is finite.

Optimality: No, as it cannot guarantee the shallowest solution.

Time complexity: A DFS, may generate all the O (bm) nodes in the search tree, where m is the maximum depth of any node; this can be much greater than the size of the state space.

Space complexity: For a search tree with branching factor b and maximum depth m, DFS requires storage of only O (bm) nodes, as at a time only the branch, which is getting explored, will reside in memory.