Graph Traversal DFS Foundation

Depth-First Search Visualizer

Explore recursive DFS with call stack frames and backtracking visualization. Watch how the recursion dives deep, pauses at each level, and backtracks when no more neighbors exist. Step through the execution to see the complete picture.

Theory

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack — either explicitly or via the call stack during recursion — to maintain the frontier of unexplored nodes. DFS is fundamental to many graph algorithms including topological sorting, cycle detection, and connectivity analysis.

Strategy: Explore deeply before exploring siblings — uses LIFO (stack) ordering to dive into branches first
Time Complexity: O(V + E) where V is vertices and E is edges in the graph
Space Complexity: O(V) for the recursion or explicit stack in the worst case
Common Applications:
- Topological sorting in directed acyclic graphs
- Detecting cycles in graphs
- Finding strongly connected components
- Solving mazes and backtracking puzzles

Problem Statement

Given a graph with nodes and edges, DFS starts from a chosen node and plunges as deep as possible before backtracking. Use the visualizer to run DFS step-by-step, observing how the stack drives the traversal and how the visited order differs fundamentally from BFS level-order expansion.

stack_structure.txt

1// LIFO Stack used by DFS
2struct Stack {
3Node* top;
4bool[] visited;
5}
6
7// push → top, pop → top (last in first out)
8// or: use recursion call stack implicitly

dfs_anatomy.svg

DFS on Tree — Example 1

tree.svg

Current

Visited

In Stack

Unvisited

Execution Mode

Stack

[ ]

Visited Order

[ ]

Start: Ready to start

DFS on Graph — Example 2

graph.svg

Current

Visited

In Stack

Unvisited

Execution Mode

Stack

[ ]

Visited Order

[ ]

Start: Ready to start

Algorithm & Pseudocode

dfs_iterative.txt

1// DFS using explicit stack
2function dfs(graph, start):
3stack = [start]
4visited = set()
5result = []
6
7while stack is not empty:
8node = stack.pop()
9if node in visited: continue
10visited.add(node)
11result.append(node)
12for neighbor in graph[node]:
13if neighbor not in visited:
14stack.push(neighbor)
15return result

dfs_recursive.txt

1// DFS using recursion
2// Call stack manages depth
3function dfs(node, graph, visited):
4visited.add(node)
5print(node)  // process node
6
7for neighbor in graph[node]:
8if neighbor not in visited:
9dfs(neighbor, graph, visited)
10
11// Backtrack here (function returns)

complexity.md

Aspect	Complexity
Time	O(V + E)
Space (Recursive)	O(V) — call stack depth
Space (Iterative)	O(V) — explicit stack

Implementation

Language:

dfs.c

1#include <stdio.h>
2#include <string.h>
3#define MAX_NODES 100
4
5// ── ITERATIVE DFS ──────────────────────
6void dfs_iterative(int adj[][MAX_NODES], int start, int n) {
7int stack[MAX_NODES], top = -1;
8int visited[MAX_NODES] = {0};
9stack[++top] = start;  // push start
10while (top >= 0) {
11int v = stack[top--];  // pop
12if (visited[v]) continue;
13visited[v] = 1;
14printf("%d ", v);
15for (int i = n-1; i >= 0; i--)  // reverse
16if (adj[v][i] && !visited[i])
17  stack[++top] = i;
18}
19}
20
21// ── RECURSIVE DFS ──────────────────────
22void dfs_recursive(int v, int adj[][MAX_NODES],
23int* visited, int n) {
24visited[v] = 1;
25printf("%d ", v);
26for (int i = 0; i < n; i++)
27if (adj[v][i] && !visited[i])
28dfs_recursive(i, adj, visited, n);
29// ↩ backtrack on return
30}
31
32int main() {
33int n = 6;
34int adj[MAX_NODES][MAX_NODES] = {0};
35adj[0][1]=adj[1][0]=1;  // 0-1
36adj[0][3]=adj[3][0]=1;  // 0-3
37adj[1][2]=adj[2][1]=1;  // 1-2
38adj[1][4]=adj[4][1]=1;  // 1-4
39adj[2][5]=adj[5][2]=1;  // 2-5
40adj[3][4]=adj[4][3]=1;  // 3-4
41
42printf("Iterative: "); dfs_iterative(adj,0,n); printf("\n");
43int visited[MAX_NODES] = {0};
44printf("Recursive: "); dfs_recursive(0,adj,visited,n); printf("\n");
45return 0;
46}

Explanation

1. Iterative DFS — Manual Stack (lines 6–19): Declares a plain int stack[] with top = -1. Push increments top before assigning; pop reads then decrements. Loop runs while top ≥ 0. Neighbors are pushed in reverse order (line 15) so the lowest-indexed neighbor surfaces on the next pop, ensuring left-to-right traversal.

2. Recursive DFS — Call Stack (lines 22–30): The OS call stack is the implicit DFS stack. Mark node visited, print it, then iterate neighbors. Each unvisited neighbor triggers a recursive call — diving deeper. When the call returns on line 28, the CPU pops the frame and continues the for-loop: that is the backtrack. Deep graphs can overflow the C stack (default ~1–8 MB).

3. Adjacency Matrix (lines 33–40): A 2-D array where adj[u][v] = 1 means an undirected edge exists. Simple to write; costs O(V²) space. Swap for an adjacency list on large sparse graphs to save memory.

4. Time & Space Complexity: Both variants run in O(V + E) — each node is visited once and each edge checked once. Space is O(V) for visited array plus O(V) worst-case stack depth. The matrix itself adds O(V²) storage regardless of edge count.

dfs.py

1from collections import defaultdict
2
3# ── ITERATIVE DFS ──────────────────────
4def dfs_iterative(graph, start):
5visited = set()
6stack   = [start]
7result  = []
8while stack:
9node = stack.pop()  # LIFO
10if node in visited:
11continue
12visited.add(node)
13result.append(node)
14for nb in reversed(graph[node]):
15if nb not in visited:
16  stack.append(nb)
17return result
18
19# ── RECURSIVE DFS ──────────────────────
20def dfs_recursive(graph, node, visited=None, result=None):
21if visited is None: visited = set()
22if result  is None: result  = []
23visited.add(node)
24result.append(node)
25for nb in graph[node]:
26if nb not in visited:
27dfs_recursive(graph, nb, visited, result)
28# ↩ backtrack on return
29return result
30
31# ── Example ────────────────────────────
32graph = defaultdict(list)
33for u, v in [('A','B'),('A','D'),('B','C'),
34('B','E'),('C','F'),('D','E'),('E','F')]:
35graph[u].append(v); graph[v].append(u)
36
37print(dfs_iterative(graph, 'A'))
38print(dfs_recursive(graph, 'A'))
39# Both → ['A', 'B', 'C', 'F', 'E', 'D']

Explanation

1. Iterative DFS — Explicit Stack (lines 4–17): Uses Python's list as a stack (.append() / .pop()). Neighbors are pushed in reversed() order (line 14) so the first neighbor surfaces on the next pop, mirroring recursive left-to-right order. The visited check on pop (line 10) handles duplicate stack entries gracefully.

2. Recursive DFS — Call Stack (lines 20–29): Python's own call stack drives the traversal. Default mutable arguments are avoided by using None sentinel defaults (lines 21–22) — a Python best practice. Each recursive call on line 27 dives deeper; returning from it is the implicit backtrack, continuing the for-loop at the caller level.

3. Graph as defaultdict (lines 32–35): Uses defaultdict(list) — an adjacency list. This is O(V + E) space vs the O(V²) matrix in C, and is idiomatic Python for sparse graphs. Both directions are appended to model an undirected edge.

4. Python vs C — Key Difference: Python's default recursion limit is 1000 frames (sys.setrecursionlimit() can raise it). For large graphs prefer iterative. Both versions run in O(V + E) time and O(V) space and produce the same traversal order.

Depth-First Search Visualizer

Theory

Problem Statement

stack_structure.txt

dfs_anatomy.svg

tree.svg

Execution Mode

Stack

Visited Order

Call Stack

Visited

Backtrack Log

graph.svg

Execution Mode

Stack

Visited Order

Call Stack

Visited

Backtrack Log

dfs_iterative.txt

dfs_recursive.txt

complexity.md

dfs.c

Explanation

dfs.py

Explanation