Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Basic Idea

Depth-first search (DFS) goes "deeper" in the graph whenever possible: it follows one branch as far as it can before backtracking.

Process:

  • keep moving to an unvisited neighbour until a dead end (e.g. a leaf) is reached
  • backtrack to the most recently visited vertex that still has an unvisited neighbour, and continue from there
  • stop when every vertex reachable from the start has been visited

Stack Implementation

DFS uses a LIFO stack, in exactly the same frame as BFS with a queue:

  • push start onto a stack s
  • while s is not empty: take the top value v, remove it from s, and visit it if it is not visited yet
  • push all unvisited adjacent vertices of v onto s, pushing them in reverse so the leftmost is on top
DFSBFS
Data structurestack (LIFO)queue (FIFO)
Take the next vertex fromtopfront
Exploresdeep first, then backtrackslevel by level

For this tree the visiting order is A B D G I H J K L C E F.

Python Code with Adjacency List

def dfs(graph, start):
    visited = [False] * (len(graph) + 1)
    stack = [start]
    order = []
    while stack:
        vertex = stack.pop()             # take the top of the stack
        if not visited[vertex]:
            order.append(vertex)
            visited[vertex] = True
            for neighbor in reversed(graph[vertex]):
                if not visited[neighbor]:
                    stack.append(neighbor)
    return order

The order is not unique: it depends on the order of each adjacency list. For the 13-vertex grid example starting at 1, the code prints 1 3 2 6 5 7 8 4 9 12 11 10 13.

Applications

Uses (BFS works for both too):

  • connectivity test: run DFS from any vertex, and the graph is connected if and only if every vertex was visited
  • unconnected graphs: if vertices remain unvisited, start a new DFS from one of them, and repeat until all are visited, each run finds one component

Time Complexity

Same as BFS: every vertex and every edge is handled a constant number of times, so DFS is .