Depth First Search (DFS)

Start here BFS spreads out carefully, layer by layer. Depth first search is the adventurous explorer: it rushes down one path as far as it can, and only when it hits a dead end does it backtrack to the last place where it had another choice. It's like exploring a maze by always taking the next unexplored turn.

The idea #

1. Start from vertex i. Pick an unexplored neighbour j.
2. Suspend (pause) the exploration of i and explore j instead.
3. Keep going deeper until you reach a vertex with no unexplored neighbours.
4. Backtrack to the most recently suspended vertex that still has an unexplored neighbour, and continue from there.

Suspended vertices are kept on a stack — last in, first out. The most recently suspended vertex is checked first.

Everyday example: Exploring a maze. At every junction you take the first passage you haven't tried. At a dead end, you walk back to the last junction with an untried passage. The trail of junctions you walked back through is your "stack".

Full trace — DFS from vertex 4 (undirected airline graph) #

Adjacency list (neighbours tried in this order): 0:[1, 2, 4], 1:[0, 2], 2:[0, 1], 3:[4, 5, 6], 4:[0, 3, 7], 5:[3, 6, 7, 8], 6:[3, 5], 7:[4, 5, 8], 8:[5, 7, 9], 9:[8].

Order in which DFS visits vertices: 4, 0, 1, 2, 3, 5, 6, 7, 8, 9.

Notice: DFS reached 2 by the path 4 – 0 – 1 – 2 (3 edges), but the shortest path is 4 – 0 – 2 (2 edges). DFS paths are not necessarily shortest.

Implementing DFS — recursion does the stack for us #

DFS is most natural as a recursive function: for each unvisited neighbour k of v, call DFS(k). The recursion itself keeps the stack of suspended calls — we don't need to manage a stack ourselves.

(visited, parent) = ({}, {})            # global dictionaries

def DFSInitListGlobal(AList):
    # Initialization
    for i in AList.keys():
        visited[i] = False
        parent[i] = -1
    return

def DFSListGlobal(AList, v):
    visited[v] = True
    for k in AList[v]:
        if (not visited[k]):
            parent[k] = v
            DFSListGlobal(AList, k)
    return

Usage:

DFSInitListGlobal(AList)
DFSListGlobal(AList, 4)

• visited and parent are global, so every recursive call updates the same dictionaries.
• We still need a separate initialization step to set them up for the size of the graph.

Result for DFS from 4: parent = {0: 4, 1: 0, 2: 1, 3: 4, 4: −1, 5: 3, 6: 5, 7: 5, 8: 7, 9: 8}.

How long does DFS take? #

Like BFS, each vertex is marked once and explored once. Exploring v means scanning all its neighbours.

Same as BFS.

Why DFS is still useful #

DFS doesn't give shortest paths, but the order in which it visits and finishes vertices reveals a lot about the graph's structure — cycles, connected pieces, and more. That's the next page.

In one line: DFS goes as deep as possible and backtracks using a stack (or recursion), takes O(n + m) with adjacency lists, but its paths are not necessarily shortest.

Exam words: DFS, suspend, backtrack, stack (LIFO), recursion keeps the stack, global visited/parent, O(n²) matrix, O(n + m) list, not shortest paths.

Quick check #