Depth-first search (DFS) explores a graph like a maze: it follows one path as deep as it can and, at a dead end, goes back and tries the next one. It needs two things: the set of visited vertices (otherwise a graph with cycles makes it loop forever) and a stack that remembers where to go back to. Graphs are stored as in Graph Representations; the examples use a dictionary of adjacency lists.

The DFS trace from A: visit order A B D E F C, the tree edges and one back edge
The DFS trace from A: visit order A B D E F C, the tree edges and one back edge

Recursive DFS

visit(u) marks the vertex and then calls itself for every neighbour not yet visited. The order of the neighbours decides the visit order.

python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def dfs(graph, start):
    visited = set()
    order = []

    def visit(u):
        visited.add(u)                    # mark on entry
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visit(v)

    visit(start)
    return order

print(dfs(graph, "A"))
text
['A', 'B', 'D', 'E', 'F', 'C']

Here D is a dead end: DFS returns to B and continues with E. Edge A-C is not used: when DFS reaches C from F, the vertex A is already visited (a back edge). The bold edges form the DFS tree.

Iterative DFS with a stack

The recursion stack can be replaced by our own: pop takes the most recently added vertex (LIFO). Pushing the neighbours with reversed gives the same visit order as the recursion.

python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}