Graph traversal: DFS and BFS
Depth-First Search (DFS) and Breadth-First Search (BFS): definitions, algorithms, properties, complexities, edge classification, and Python implementations with sample I/O.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Graph traversal is fundamental to solve connectivity, reachability, and shortest-path problems in networks, compilers, operating systems, and web crawlers. Breadth-First Search (BFS) and Depth-First Search (DFS) are the two standard traversal algorithms used to explore all vertices/edges systematically, form trees of exploration, and support higher-level algorithms like Dijkstra’s shortest path, topological sorting, and minimum spanning trees.
Key ideas
- Adjacency list representation: For each vertex u, store a list of neighbors Adj[u]. Space is Θ(V + E). Efficient for sparse graphs.
- Adjacency matrix representation: A V×V matrix A, where A[u][v] = 1 if edge (u, v) exists else 0 (or boolean). Space is Θ(V²). Efficient to test edge existence in O(1).
- Traversal: Systematic visit of vertices and edges, marking visited to avoid repeats. Output often includes a traversal order and a parent relation forming a traversal tree or forest.
- Breadth-First Search (BFS): An algorithm that explores the graph level by level starting from a source vertex s, visiting all vertices at distance 1, then distance 2, and so on, using a queue (FIFO). Assumes all edges have equal weight (unweighted graph) for shortest-path property.
- Exact property (Shortest path in unweighted graphs): Given an unweighted graph and a source s, BFS computes for every reachable vertex v a shortest path P(s, v) in terms of minimum number of edges; the distance dist[v] equals the number of edges on the shortest path.
- Data maintained: color/visited flag, parent π[v], and dist[v] (integer levels).
- Depth-First Search (DFS): An algorithm that explores as far as possible along one branch before backtracking, using recursion or an explicit stack (LIFO). Produces a DFS tree (or forest) and timestamps.
- Discovery time d[u]: The time when vertex u is first visited.
- Finish time f[u]: The time when DFS finishes exploring all edges from u (and returns).
- Standard invariant: For any vertex u, d[u] < f[u]. Each time is unique if we increment a global clock by 1 per event.
- Edge classification in DFS (directed graphs): For a directed graph, each edge (u, v) during a complete DFS can be classified as:
- Tree edge: v was white when (u, v) explored; v becomes a child of u in DFS tree.
- Back edge: Edge to an ancestor in the DFS tree (v is an ancestor of u). Time property: d[v] < d[u] < f[u] < f[v]. Includes self-loops as back edges.
- Forward edge: Edge to a descendant in the DFS tree (v is a proper descendant of u). Time property: d[u] < d[v] < f[v] < f[u].
- Cross edge: Any other edge between two different DFS subtrees or between vertices where neither is ancestor of the other. Time property pattern: d[v] < f[v] < d[u] < f[u] (or the reverse with u and v swapped) when (u, v) is cross.
- Assumption: Complete DFS over all vertices in ascending order if not connected; classification uses discovery/finish times after the run. In undirected graphs, DFS produces only tree and back edges (no forward or cross edges); an undirected graph is acyclic iff DFS finds no back edge (equivalently, every visited neighbor is either unvisited or the parent).
- Complexity (Adjacency list): Both BFS and DFS run in time Θ(V + E) and use space Θ(V) for metadata (visited/parent/dist) plus Θ(V + E) for the graph.
- Complexity (Adjacency matrix): BFS and DFS run in Θ(V²) time due to scanning V neighbors per vertex; space Θ(V²) for the matrix and Θ(V) for metadata.
- Traversal trees:
- BFS tree: A shortest-path tree from the source; parent pointers give shortest paths by edge count.
- DFS tree (forest): Parent pointers define depth-first structure; discovery/finish intervals [d[u], f[u]] are nested: for a tree edge (u, v), interval of v is strictly inside interval of u.
- When to use:
- Use BFS for shortest paths in unweighted graphs, levels, and bipartite checking (via 2-coloring/level parity; no edge should connect same-colored/same-level vertices).
- Use DFS for cycle detection, topological sorting in DAGs, strongly connected components (as a step in Kosaraju/Tarjan), and edge classification.
- Diagram to draw in exams (BFS vs DFS on same graph): Draw 6–8 vertices labeled 0..7 placed roughly like a hexagon or grid; draw undirected edges clearly. For BFS: draw levels from the source s = 0 as concentric layers or rows, label dist on each vertex, and draw parent arrows forming the BFS tree. For DFS: draw discovery/finish times near each vertex (e.g., d/f), arrows for tree edges, and dotted arrows for non-tree edges; show the stack/backtracking order.
- Proof sketch (BFS shortest path):
- Induction on levels: Base level dist[s] = 0. Assume all vertices at level k have correct dist = k.
- Each undiscovered neighbor of any level-k vertex gets dist = k + 1 when first discovered.
- No shorter path can exist: any path from s to a vertex at level k + 1 must pass through at least one vertex at level k; hence ≥ k + 1 edges.
- Proof sketch (DFS time-nesting):
- For any tree edge (u, v), all of v’s descendants are explored before u finishes; thus d[u] < d[v] < f[v] < f[u]. Back edges go to an ancestor still on stack (gray), giving d[v] < d[u] < f[u] < f[v].
Formulas
Programming syntax and patterns to remember:
queue = collections.deque(); queue.append(x); x = queue.popleft()— FIFO queue for BFS. No physical units; Python container operations when exploring breadth-first.stack = []; stack.append(x); x = stack.pop()— LIFO stack for iterative DFS. No units; Python list used as stack.visited = [False]*n; parent = [-1]*n; dist = [∞]*n— BFS/DFS metadata arrays;∞can be a large sentinel like10**18.for v in adj[u]:— Iterate over adjacency list neighbors.adj = [[] for _ in range(n)]— Build adjacency list for 0..n−1.sys.setrecursionlimit(...)— Increase recursion limit for deep DFS in Python if needed (use with care).time += 1; d[u] = time; ... time += 1; f[u] = time— Maintain discovery/finish timestamps in DFS.
Worked examples
Example 1: BFS and DFS traversals on an undirected graph (orders, parents, distances) Complete Python program (uses adjacency lists, deterministic by sorting neighbors):
# Program 1: BFS and recursive DFS on an undirected graph
# Input format:
# n m
# m lines of edges: u v (0-based, undirected)
# s (source for BFS and DFS)
import sys
from collections import deque
def read_graph():
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
m = int(next(it))
adj = [[] for _ in range(n)]
for _ in range(m):
u = int(next(it)); v = int(next(it))
adj[u].append(v)
adj[v].append(u)
s = int(next(it))
for u in range(n):
adj[u].sort()
return n, adj, s
def bfs(n, adj, s):
visited = [False]*n
parent = [-1]*n
INF = 10**18
dist = [INF]*n
order = []
q = deque()
visited[s] = True
dist[s] = 0
q.append(s)
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
dist[v] = dist[u] + 1
q.append(v)
return order, parent, dist
sys.setrecursionlimit(1_000_000)
def dfs_recursive(n, adj, s):
visited = [False]*n
order = []
parent = [-1]*n
def dfs(u):
visited[u] = True
order.append(u)
for v in adj[u]:
if not visited[v]:
parent[v] = u
dfs(v)
dfs(s)
return order, parent
if __name__ == "__main__":
n, adj, s = read_graph()
b_order, b_parent, b_dist = bfs(n, adj, s)
d_order, d_parent = dfs_recursive(n, adj, s)
print("BFS order:", " ".join(map(str, b_order)))
print("BFS parent:", " ".join(map(str, b_parent)))
print("BFS dist:", " ".join(map(str, b_dist)))
print("DFS order:", " ".join(map(str, d_order)))
print("DFS parent:", " ".join(map(str, d_parent)))
Sample input
5 6
0 1
0 2
1 3
1 4
2 3
3 4
0
Exact output
BFS order: 0 1 2 3 4
BFS parent: -1 0 0 1 1
BFS dist: 0 1 1 2 2
DFS order: 0 1 3 2 4
DFS parent: -1 0 3 1 3
Explanation checks:
- BFS discovers 1 and 2 at level 1 from 0; 3 and 4 at level 2. Parents show shortest-path tree.
- DFS (neighbors in ascending order) goes 0→1→3→2 (backtrack)→4.
Example 2: DFS times and edge classification on a directed graph Complete Python program (classifies edges after a full DFS; neighbors processed in ascending order for determinism):
# Program 2: DFS discovery/finish times and edge classification (directed graph)
# Input format:
# n m
# m lines of directed edges: u v (0-based)
import sys
def read_graph():
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
m = int(next(it))
adj = [[] for _ in range(n)]
edges = []
for _ in range(m):
u = int(next(it)); v = int(next(it))
adj[u].append(v)
edges.append((u, v))
for u in range(n):
adj[u].sort()
return n, adj, edges
sys.setrecursionlimit(1_000_000)
def dfs_full(n, adj):
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE]*n
parent = [-1]*n
d = [0]*n
f = [0]*n
time = 0
def dfs_visit(u):
nonlocal time
color[u] = GRAY
time += 1
d[u] = time
for v in adj[u]:
if color[v] == WHITE:
parent[v] = u
dfs_visit(v)
color[u] = BLACK
time += 1
f[u] = time
for u in range(n):
if color[u] == WHITE:
dfs_visit(u)
return d, f, parent
if __name__ == "__main__":
n, adj, edges = read_graph()
d, f, parent = dfs_full(n, adj)
# Classify edges using discovery/finish times
def classify(u, v):
# Tree edge: parent[v] == u
if parent[v] == u:
return "Tree"
# Back edge: v is ancestor of u ⇒ d[v] < d[u] < f[u] < f[v]
if d[v] < d[u] and f[u] < f[v]:
return "Back"
# Forward edge: v is descendant of u ⇒ d[u] < d[v] < f[v] < f[u]
if d[u] < d[v] and f[v] < f[u]:
return "Forward"
# Otherwise cross
return "Cross"
print("Times (vertex: d/f)")
for u in range(n):
print(f"{u}: {d[u]}/{f[u]}")
print("Edges and types (in input order)")
for (u, v) in edges:
print(f"{u} {v}: {classify(u, v)}")
Sample input
5 7
0 1
0 2
1 2
1 3
2 4
3 4
4 1
Exact output
Times (vertex: d/f)
0: 1/10
1: 2/9
2: 3/6
3: 7/8
4: 4/5
Edges and types (in input order)
0 1: Tree
0 2: Forward
1 2: Tree
1 3: Tree
2 4: Tree
3 4: Cross
4 1: Back
Model theory answer fragment (to practice writing):
- Definition: In a directed graph, after a complete DFS, each edge is Tree, Back, Forward, or Cross. For Tree edges (u, v), d[u] < d[v] < f[v] < f[u]. For Back edges to an ancestor (including self-loops), d[v] < d[u] < f[u] < f[v]. For Forward edges (u, v) to a descendant, d[u] < d[v] < f[v] < f[u]. All remaining edges are Cross.
- Application: Cycle detection — a directed graph has a cycle iff DFS finds a Back edge.
Common mistakes
- Forgetting to initialize visited/parent/dist for all vertices; leaving garbage values.
- Not handling disconnected graphs: failing to start new BFS/DFS from unvisited vertices (needed for full traversal or classification over all vertices).
- Assuming BFS gives shortest weighted paths (it only guarantees shortest paths by number of edges in unweighted graphs or equally weighted edges).
- Non-deterministic traversal order in answers: not stating the neighbor visitation order (e.g., ascending vertex id) causing mismatched sequences compared to expected answers.
- In DFS, misclassifying edges because discovery/finish times were not recorded or because classification used only colors after recursion finished.
- Stack overflow in recursive DFS on very deep graphs; not considering iterative DFS or recursion limit.
- For adjacency matrix, incorrectly claiming O(V + E) time; it is O(V²) due to scanning all V neighbors per vertex.
For your exam
- Short notes: Compare BFS vs DFS (strategy, data structure, complexity, use-cases). Space/time complexities for both adjacency list and matrix.
- Derivations/proofs: BFS shortest-path correctness (level argument). DFS properties with time intervals and edge classification inequalities. Condition for cycle detection via Back edges.
- Programs: Implement BFS and DFS, print traversal order, parents, distances; program to compute discovery/finish times and classify edges. Ensure deterministic neighbor order and exact I/O format.
- Diagrams: Same graph traversed by BFS and DFS from a given source; show BFS levels and DFS d/f timestamps, label tree vs non-tree edges. Clearly label vertices and edges; state neighbor visitation order used (e.g., ascending ids).
- Full-marks answers include: clean pseudocode or working code, correct complexity, correct traversal orders based on stated neighbor order, correct parent/dist arrays for BFS, correct d/f times and edge classifications for DFS, and a brief justification of key properties.
Quick check
- What is the time complexity of BFS on a graph with V vertices and E edges stored in an adjacency list? What about adjacency matrix?
- Which traversal guarantees shortest paths by number of edges in an unweighted graph from a single source, and how is the shortest path length obtained?
- In DFS on a directed graph, how do you identify a Back edge using discovery and finish times of its endpoints (u, v)?
Answers: 1) Adjacency list: Θ(V + E). Adjacency matrix: Θ(V²). 2) BFS; the shortest path length to v is dist[v], set when v is first discovered. 3) It is a Back edge if d[v] < d[u] < f[u] < f[v] (v is an ancestor of u).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?