DSA Graph Traversal — BFS & DFS Visualized
Learn graph traversal — BFS with queue, DFS with stack/recursion, step-by-step visualizer, annotated code, and shortest-path use cases.
Introduction
Graph traversal visits every reachable vertex exactly once. BFS (breadth-first) uses a queue; DFS (depth-first) uses a stack or recursion.
Both run in O(V + E) and underpin shortest paths, connectivity, and cycle detection.
Quick index
1. BFS vs DFS
Sample graph from A:
A
/ \
B C
/ \ \
D E F| Algorithm | Order from A | Data structure |
|---|---|---|
| BFS | A → B → C → D → E → F | Queue (FIFO) |
| DFS | A → B → D → E → C → F | Stack (LIFO) |
BFS explores level by level; DFS goes deep before backtracking.
2. Interactive visualizer
Graph Traversal — BFS & DFS
BFS uses a queue for level-order exploration; DFS uses a stack (or recursion) for depth-first paths.
BFS from A — explore all reachable vertices level-by-level.
BFS skeleton
function bfs(graph, start) {
const queue = [start], visited = new Set([start])
const order = []
while (queue.length) {
const node = queue.shift()
order.push(node)
for (const n of graph[node]) {
if (!visited.has(n)) { visited.add(n); queue.push(n) }
}
}
return order
}Queue (FIFO) drives exploration order.
BFS
Queue
DFS
Stack
Time
O(V+E)
3. Full implementation
function bfs(graph, start) {
const queue = [start]
const visited = new Set([start])
const order = []
while (queue.length) {
const node = queue.shift()
order.push(node)
for (const neighbor of graph[node] ?? []) {
if (!visited.has(neighbor)) {
visited.add(neighbor)
queue.push(neighbor)
}
}
}
return order
}
function dfs(graph, start) {
const visited = new Set()
const order = []
function explore(node) {
visited.add(node)
order.push(node)
for (const neighbor of graph[node] ?? []) {
if (!visited.has(neighbor)) explore(neighbor)
}
}
explore(start)
return order
}
function bfsShortestPath(graph, start, target) {
const queue = [[start, [start]]]
const visited = new Set([start])
while (queue.length) {
const [node, path] = queue.shift()
if (node === target) return path
for (const neighbor of graph[node] ?? []) {
if (!visited.has(neighbor)) {
visited.add(neighbor)
queue.push([neighbor, [...path, neighbor]])
}
}
}
return null
}Function calls with output
// ── Demo calls — output shown on the right ──
const graph = {
A: ['B', 'C'],
B: ['A', 'D', 'E'],
C: ['A', 'F'],
D: ['B'],
E: ['B'],
F: ['C'],
}
bfs(graph, 'A') // → ['A', 'B', 'C', 'D', 'E', 'F']
dfs(graph, 'A') // → ['A', 'B', 'D', 'E', 'C', 'F']
bfsShortestPath(graph, 'A', 'F') // → ['A', 'C', 'F']
bfsShortestPath(graph, 'D', 'F') // → ['D', 'B', 'A', 'C', 'F']4. When to use
| Use case | Algorithm | Why |
|---|---|---|
| Shortest path (unweighted) | BFS | First arrival = fewest edges |
| Detect connected components | BFS or DFS | Either works |
| Topological sort | DFS | Post-order finish times |
| Maze solving | DFS | Explore one path fully |
| Social degrees of separation | BFS | Level = hop count |
5. Real-life examples
| Scenario | Traversal |
|---|---|
| Six degrees of Kevin Bacon | BFS — each level = one film hop |
| Web crawler | BFS — index pages breadth-first |
| File system search | DFS — drill into directories first |
| GPS (unweighted hops) | BFS — minimum number of turns |
Six degrees — BFS on actor graph
Find shortest connection between two actors through shared films — classic BFS level-by-level.
Start: Kevin Bacon
Level 0: [Kevin Bacon]
Queue: [(Kevin, 0)]
BFS begins at source — depth 0.
Real-world implementation
function degreesOfSeparation(graph, start, target) {
const queue = [[start, 0]]
const visited = new Set([start])
while (queue.length) {
const [person, depth] = queue.shift()
if (person === target) return depth
for (const coStar of graph[person] ?? []) {
if (!visited.has(coStar)) {
visited.add(coStar)
queue.push([coStar, depth + 1])
}
}
}
return -1
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ── degreesOfSeparation(graph, "Kevin Bacon", "Tom Hanks")
Side output shows return value after each call — step through to trace execution.
Summary
BFS for shortest paths and level-order; DFS for deep exploration and topological sort. Both are O(V + E).
Next reads: Cycle Detection · Graphs Implementation
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime