Depth-First Search

Breadth-first search advanced by distance: nothing farther away was visited before everything nearby had been. Depth-first search follows the opposite strategy — it follows a path until it is blocked, then returns to the last branching point and tries another branch.

The structural difference is in a single place: a stack is used instead of a queue. Whatever separates level-order and depth traversal in trees separates these two here as well.

Recursive Form

The stack need not be kept explicitly; recursion uses the call stack for the same purpose.

def depth_first_search(adjacency: dict[str, list[str]], start: str) -> list[str]:
    """Traverses depth-first; returns the visit order."""
    visited: set[str] = set()
    order: list[str] = []

    def visit(vertex: str) -> None:
        visited.add(vertex)
        order.append(vertex)
        for neighbor in adjacency.get(vertex, []):
            if neighbor not in visited:
                visit(neighbor)                  # descend until blocked

    visit(start)
    return order


adjacency = {
    "west":   ["north", "south"],
    "north":  ["west", "center"],
    "south":  ["west", "center"],
    "center": ["north", "south", "east"],
    "east":   ["center"],
}

print(depth_first_search(adjacency, "west"))
# ['west', 'north', 'center', 'south', 'east']

On the same graph, breadth-first search gave the order ['west', 'north', 'south', 'center', 'east']. In depth-first search, center is descended into immediately from north; south is only visited once that branch is exhausted.

Explicit-Stack Form

The transformation built in the Programming Fundamentals course applies here as well: an explicit stack can be kept instead of the call stack. In deep graphs this avoids hitting the recursion limit.

def depth_first_search_stack(adjacency: dict[str, list[str]], start: str) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []
    stack = [start]
    while stack:
        vertex = stack.pop()                     # last in, first out
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        for neighbor in reversed(adjacency.get(vertex, [])):
            if neighbor not in visited:
                stack.append(neighbor)            # push in reverse: preserves order

    return order


print(depth_first_search_stack(adjacency, "west"))
# ['west', 'north', 'center', 'south', 'east']

Pushing neighbors in reverse order rests on the same reasoning as pushing the right child first in tree traversals: a stack returns items in the reverse of the order they were pushed.

There is a subtle difference between the two forms: in the explicit-stack version, a vertex can be pushed onto the stack more than once before being visited. For this reason it is rechecked when popped. Memory use rises somewhat; behavior stays the same.

Discovery and Finish Times

The extra information depth-first search carries is two timestamps for each vertex:

• Discovery time: The moment the vertex is first reached.
• Finish time: The moment control returns to it after all its descendants have been visited.

These two values make it possible to classify the relationship between vertices. If one vertex’s discovery–finish interval fully contains another’s, the second is a descendant of the first; if the intervals do not overlap, the two vertices are in separate branches. Intervals can never partially overlap — this is a direct consequence of the stack structure of the traversal.

Finish times form the basis of the topological sort taken up in the next lesson.

Cycle Detection

One of the most common uses of depth-first search is looking for a cycle in a directed graph. The distinction is between “visited” and “still on the stack”: if the traversal returns to a vertex that is still open, a cycle exists.

def has_cycle(adjacency: dict[str, list[str]]) -> bool:
    """Tests whether a directed graph contains a cycle."""
    visited: set[str] = set()
    open_set: set[str] = set()                   # currently on the stack

    def visit(vertex: str) -> bool:
        visited.add(vertex)
        open_set.add(vertex)
        for neighbor in adjacency.get(vertex, []):
            if neighbor in open_set:
                return True                       # back edge: cycle
            if neighbor not in visited and visit(neighbor):
                return True
        open_set.discard(vertex)                  # branch completed
        return False

    return any(visit(v) for v in adjacency if v not in visited)


acyclic = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
cyclic = {"a": ["b"], "b": ["c"], "c": ["a"]}

print(has_cycle(acyclic))     # False
print(has_cycle(cyclic))      # True

Without the open_set, testing with visited alone gives a wrong result: in the acyclic graph, vertex d is reached by two different paths, but this is not a cycle. Separating the two concepts is therefore necessary.

Comparing the Two Traversals

Criterion	Breadth-first search	Depth-first search
Auxiliary structure	Queue	Stack (or recursion)
Advance	Layer by layer	Deep along a branch
Unweighted shortest path	Finds it	Does not
Memory	Widest layer	Deepest path
Natural use	Distance, spread, fewest steps	Cycles, ordering, backtracking
Cost	$O(V + E)$	$O(V + E)$

The fourth row can be decisive in a practical choice: in a wide, shallow graph, the queue in breadth-first search grows very large; in a deep, narrow graph, the stack in depth-first search does.

The third row is the source of the most common mistake: depth-first search finds a path, but there is no guarantee that the path it finds is the shortest.

Iterative Deepening

The comparison table shows a dilemma: breadth-first search finds the shortest path but can use a great deal of memory; depth-first search uses little memory but does not find the shortest path.

Iterative deepening combines the two. Depth-first search is first run with a depth limit of one; if no solution is found, the limit is raised to two, and the search is run again from the start. The limit keeps rising as the search deepens.

At first glance this looks wasteful — the same upper layers are revisited again and again. But when the branching factor is greater than one, most of the vertices are in the last layer; the repeated work remains a small fraction of the total. The cost ends up in the same order as breadth-first search.

The gain is in memory: only a single path is kept on the stack at any moment. The first solution found is also the shallowest one, because no solution was found at smaller limits.

The method is preferred in problems where the search space is not known in advance and does not fit in memory — game-tree search, puzzle solving.

Uses

• Cycle detection. As above; the validity of dependency graphs is checked with this test.
• Connected components. As with breadth-first search, a traversal is started from every unvisited vertex.
• Topological sort. The reverse of finish times gives a valid ordering; the subject of the next lesson.
• Backtracking. Maze solving, puzzle filling, and constraint-satisfaction problems are applications of depth-first search over a choice tree.
• Path finding. When any path between two vertices is wanted — not necessarily the shortest — depth-first search produces a result with less memory.

Summary

• Depth-first search follows a path until it is blocked, then returns to the last branching point; it uses a stack instead of a queue.
• The recursive form uses the call stack; the explicit-stack form is safe in deep graphs.
• Discovery and finish times encode the ancestry relationship between vertices; intervals either contain one another or are disjoint.
• Cycle detection requires distinguishing “visited” from “still open.”
• Breadth-first search finds the shortest path, depth-first search does not; their memory behavior diverges according to the shape of the graph.
• Both traversals cost $O(V + E)$.

Next Step

In graphs that model dependency relationships, the real question is this: in what order should the work be done? The final lesson of the course takes up topological sort, which produces a valid execution order in directed acyclic graphs, and brings together the structures this course has built.