Depth-first search (DFS)

Diving as deep as possible

The depth-first search (DFS) adopts the opposite strategy to BFS: instead of exploring breadth-wise, it dives into a branch all the way down, then backtracks to explore the unvisited branches. It is the strategy we instinctively use to get out of a maze: follow a corridor to the wall, then turn back.

Start at A, DFS :

        (A)                possible order :  A  B  D  E  C
        /  \                (we dive A->B->D, wall,
      (B)   (C)              we come back up, B->E, wall,
      /  \                   we come back up to A, then C)
    (D)   (E)

Recursive version: the most natural

DFS is written very elegantly with recursion, which implicitly uses the call stack.

def dfs(graphe, s, visites=None):
    if visites is None:
        visites = set()
    visites.add(s)                 # (mark as visited)
    print(s, end=" ")
    for voisin in graphe[s]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)   # (we dive !)

The recursive call "dives" into the neighbour before processing the next ones: this is exactly what produces the descent in depth.

Iterative version: with a stack

We can also write it without recursion, by replacing the queue of BFS with a stack (LIFO). This is the only fundamental change between the two traversals.

def dfs_iteratif(graphe, depart):
    visites = set()
    pile = [depart]
    while pile:
        s = pile.pop()             # (we take out the MOST RECENT : LIFO)
        if s not in visites:
            visites.add(s)
            print(s, end=" ")
            for voisin in graphe[s]:
                pile.append(voisin)

BFS or DFS: the same skeleton, one data structure

This is the most important point of the chapter. BFS and DFS are the same algorithm: start from a vertex, remove an element from a store, process it, add its unvisited neighbours to it. Only the nature of the store changes the order of exploration:

Traversal	Store	Behaviour	Finds the shortest path?
BFS	queue (FIFO)	in waves, breadth-wise	yes (unweighted)
DFS	stack (LIFO)	dives in depth	no

What is DFS used for?

DFS excels at problems where you need to explore all the possibilities: detecting a cycle, finding the connected components (the "islands" of a graph), solving a maze, or doing a topological sort (ordering tasks according to their dependencies).

In summary

DFS dives to the bottom of a branch before backtracking, using the stack (explicit, or implicit via recursion). It shares exactly the same structure as BFS: replacing the queue with a stack is enough to switch from one to the other. DFS does not guarantee the shortest path, but it is ideal for exhaustively exploring a graph.