Graph DFS

Traverse a graph by exploring as deep as possible before backtracking.

O(V + E)Graphs
Phase 1f(x)

The Mathematics

Depth-first exploration, stack structure, and edge classification

Core Idea

DFS explores a graph G=(V,E)G = (V, E) by going as deep as possible along each branch before backtracking. It uses a stack (implicit via recursion or explicit):

DFS(v):visit v, then ∀u∈Adj(v) if u∉visited:DFS(u)\text{DFS}(v): \text{visit } v, \text{ then } \forall u \in \text{Adj}(v) \text{ if } u \notin \text{visited}: \text{DFS}(u)

DFS vs. BFS

While BFS uses a FIFO queue (layer-by-layer), DFS uses a LIFO stack (depth-first). BFS finds shortest paths in unweighted graphs; DFS is useful for topological sorting, cycle detection, and connected components.

BFS

Queue (FIFO)\text{Queue (FIFO)}

Layer-by-layer

DFS

Stack (LIFO)\text{Stack (LIFO)}

Depth-first

Edge Classification

DFS classifies edges in the graph:

∙\bullet Tree edges: edges in the DFS tree (to unvisited vertices)

∙\bullet Back edges: edges to an ancestor (indicate a cycle)

∙\bullet Forward/Cross edges: edges to already-finished vertices

Complexity

Every vertex is visited exactly once, and every edge is examined once (twice for undirected graphs):

T(V,E)=O(∣V∣+∣E∣)T(V, E) = O(|V| + |E|)

Same asymptotic complexity as BFS, but the traversal order is fundamentally different.

Phase 2▶

See It Work

DFS traversal from node A — watch the recursive stack

ABCDEFG

Call Stack (LIFO)

bottom
A
top
DFS(s):visited={A}\text{DFS}(s): \text{visited} = \{A\}
Step 1 of 9

Start DFS from node A. Mark A as visited and begin exploring.

Phase 3</>

The Code

Mapping recursive DFS to Python with a nested explore function

Mathematical Formulation

visited=∅\text{visited} = \emptyset

Initialize empty visited set to track explored vertices

visited←visited∪{v}\text{visited} \leftarrow \text{visited} \cup \{v\}

Mark the current vertex as visited

∀u∈Adj(v)\forall u \in \text{Adj}(v)

Iterate over all neighbors of the current vertex

u∉visited⇒explore(u)u \notin \text{visited} \Rightarrow \text{explore}(u)

Recursively explore unvisited neighbors — go deep first

O(∣V∣+∣E∣)O(|V| + |E|)

Each vertex visited once, each edge checked once

Python Implementation

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

    def explore(v):
        visited.add(v)              # Mark visited
        order.append(v)             # Record order
        for u in graph[v]:          # Visit neighbors
            if u not in visited:    # Skip if seen
                explore(u)          # Recurse deeper

    explore(source)
    return order