Graph Traversal: BFS, DFS and Visited Sets
Turn a graph into an adjacency list, reason about traversal order and avoid infinite cycles using visited nodes.
Key Learning Objectives
- Represent a graph using neighbors for each vertex.
- Implement breadth-first traversal.
- Distinguish shortest unweighted distance from DFS reachability.
- Handle cycles and disconnected components.
Draw vertices and edges before coding
A graph models relationships. An adjacency list stores neighbors for each vertex, usually using O(V+E) memory for V vertices and E edges. It suits sparse graphs because it does not allocate a dense V-by-V table. Decide whether edges are directed and whether a node can have a self-loop or repeated edge. Those details change expected traversal behavior.
BFS explores by layers
Breadth-first search uses a queue. Mark a node visited when you enqueue it, not when you remove it, so the same node is not placed in the queue repeatedly. In an unweighted graph, the first time you discover a node gives a shortest edge-count distance from the source. Every vertex and edge is processed at most a constant number of times, so traversal takes O(V+E) time.
function bfs(graph: Record<string, string[]>, start: string): string[] {
const seen = new Set([start]);
const queue = [start]; const order: string[] = [];
for (let head = 0; head < queue.length; head++) {
const node = queue[head]; order.push(node);
for (const next of graph[node] || []) {
if (!seen.has(next)) { seen.add(next); queue.push(next); }
}
}
return order;
}
A head index avoids costly Array.shift calls; the visited set prevents repeated exploration.
DFS answers different questions
Depth-first search explores one branch before backtracking, often using recursion or an explicit stack. It is useful for connectivity, component counting and cycle-related algorithms; it does not generally find a shortest unweighted path without extra work. For a disconnected graph, a traversal from one source covers only its reachable component—loop over all vertices if your goal is to visit every component.
Build It: Campus connection explorer
Given a small graph of clubs and members, report reachability and minimum number of connections.
Project Deliverables
- Adjacency-list representation.
- BFS with distances.
- DFS with component count.
Acceptance Criteria
- Cycles do not loop forever.
- Disconnected nodes remain unreachable.
- Distance from a node to itself is zero.
Next Steps & Related Learning
This interactive lesson is part of the Data Structures & Algorithms curriculum. Continue exploring or try another interactive lesson: