Graph Traversal (BFS/DFS) — Mathematics Knowledge System

Overview

Graph traversal is the process of systematically visiting every vertex in a graph. The two fundamental strategies are breadth-first search (BFS), which explores all neighbors of a vertex before moving further out, and depth-first search (DFS), which plunges as deep as possible along one branch before backtracking. Tree traversal is a special case of graph traversal. These algorithms are the foundation on which shortest-path, connectivity, and cycle-detection algorithms are built.

Intuition

BFS explores like ripples spreading outward from a stone dropped in a pond — it visits everything at distance 1, then everything at distance 2, and so on, using a queue (first-in-first-out) to track what to visit next. DFS explores like a person in a maze who always takes an unexplored corridor and only backtracks when stuck — using a stack (or recursion) to remember the path back.

Interactive Graph

Formal Definition

Definition

Both algorithms take a graph G = (V, E) and a start vertex s and produce an order in which vertices are discovered, using a 'visited' set to avoid repeats:

\text{BFS}(G, s):\ \text{visit } s,\ \text{enqueue } s;\ \text{while queue nonempty, dequeue } u,\ \text{visit unvisited neighbors of } u,\ \text{enqueue them}

Queue-based, level-by-level exploration

\text{DFS}(G, s):\ \text{visit } s;\ \text{for each unvisited neighbor } v \text{ of } s,\ \text{recursively call } \text{DFS}(G, v)

Stack-based (or recursive) exploration, depth-first

Notation

Notation	Meaning
$\text{BFS}$	Breadth-first search
$\text{DFS}$	Depth-first search
$d(v)$	BFS distance — number of edges on the shortest path from the source to v

Properties

BFS finds shortest paths (unweighted)

d(v) = \text{minimum number of edges from } s \text{ to } v

Condition: Only holds for unweighted (or equal-weight) graphs

Time complexity

O(|V| + |E|)

Example: Both BFS and DFS visit each vertex once and examine each edge once (with an adjacency list)

DFS produces a DFS tree / forest

\text{Tree edges, back edges, forward edges, and cross edges classify all edges relative to the DFS traversal}

Applications

BFS is used for shortest paths in unweighted graphs and for level-order processing (e.g. web crawlers exploring by link distance); DFS is used for topological sorting, cycle detection, and finding connected components.

Worked Examples

Visit A, enqueue its neighbors B and C (alphabetical order).
$\text{Visited: } A$
Dequeue B, visit it, enqueue its unvisited neighbor D.
$\text{Visited: } A, B$
Dequeue C, visit it; D is already enqueued so nothing new is added.
$\text{Visited: } A, B, C$
Dequeue D, visit it; all neighbors already visited.
$\text{Visited: } A, B, C, D$

Answer: A, B, C, D

Practice Problems

Difficulty 3/10

A graph has 6 vertices and 9 edges, represented as an adjacency list. What is the time complexity of running BFS on it?

Difficulty 4/10

Which data structure does BFS use to decide which vertex to explore next?

A stackA queueA priority queueA hash set only

Difficulty 5/10

You must find the FEWEST-step path out of a grid maze (each move costs the same). Should you use BFS or DFS, and why?

Difficulty 5/10

A build system needs to detect a circular dependency among tasks. Which traversal detects a cycle in a directed graph, and what signals the cycle?

Common Mistakes

Common Mistake

Believing DFS also finds shortest paths in unweighted graphs.

Only BFS guarantees shortest paths (in edge count) in unweighted graphs, because it explores level-by-level. DFS may reach a vertex via a long, winding path first.

Common Mistake

Forgetting to mark vertices as visited before or as soon as they are enqueued in BFS, leading to duplicate enqueues.

Mark a vertex visited at the moment it is enqueued (not when dequeued) — otherwise the same vertex can be added to the queue multiple times via different neighbors.

Quiz

Summary

Graph traversal visits every vertex in a graph; BFS and DFS are the two fundamental strategies.
BFS uses a queue and explores level-by-level; it finds shortest paths in unweighted graphs.
DFS uses a stack (or recursion) and explores as deep as possible before backtracking.
Both run in O(|V| + |E|) time with an adjacency-list representation.
DFS underlies topological sort, cycle detection, and connected-component algorithms.

References

WebsiteWikipedia — Graph traversal