Graph Traversal: BFS & DFS — Data Structures Course

What you'll learn

There are two fundamental ways to explore a graph, and they differ by a single data structure. BFS uses a queue and spreads out level by level; DFS uses a stack (or recursion) and plunges deep. Both visit every vertex in O(V + E).

By the end you'll be able to:

Run BFS with a queue and DFS with a stack / recursion
Track a visited set to avoid revisiting (graphs have cycles!)
Pick BFS or DFS for a given problem

Breadth-first search

BFS explores all neighbors of a vertex before going deeper — rippling outward from the start. It uses a queue: dequeue a node, visit it, enqueue its undiscovered neighbors. Because it goes level by level, BFS finds the shortest path in edges on an unweighted graph.

BFS from A

Breadth-first search

1/14BFS from A: put A in the queue. The frontier (yellow) is what's waiting.

Yellow = frontier (in the queue) · blue = visiting now · green = done.

Depth-first search

DFS goes as deep as it can, then backtracks. It's naturally recursive (the call stack is the stack). DFS underlies cycle detection, topological sort, connected components, and maze solving.

DFS from A

Depth-first search

1/8DFS from A: dive as deep as possible before backtracking.

Blue = visiting now · green = already visited. Notice how it dives deep before spreading.

Watch out

Unlike trees, graphs can have cycles. Always keep a visited set — without it, both BFS and DFS can loop forever.

In code

The only real difference is queue vs stack:

Language

bfs.py

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()       # a QUEUE → breadth-first
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

Language

dfs.py

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    visit(node)
    for nb in graph[node]:           # recursion = an implicit STACK
        if nb not in visited:
            dfs(graph, nb, visited)

# iterative version uses an explicit stack:
def dfs_iter(graph, start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()           # a STACK → depth-first
        if node not in visited:
            visited.add(node); visit(node)
            stack.extend(graph[node])

BFS vs DFS

	BFS	DFS
`Structure`	Queue (FIFO)	Stack / recursion
`Explores`	Level by level	Deep, then backtracks
`Finds`	Shortest path (unweighted)	Any path; cycles; ordering
`Memory`	O(width) — can be wide	O(depth) — the recursion depth
`Time`	O(V + E)	O(V + E)

Recap & quick check

Key takeaways

BFS uses a queue and explores level by level; DFS uses a stack/recursion and goes deep.
Both are O(V + E) and need a visited set because graphs can have cycles.
BFS finds the shortest path (fewest edges) in an unweighted graph.
DFS underpins cycle detection, topological sort, and connected components.
The only structural difference between them is queue vs stack.

Quick check

1. Which data structure makes a traversal breadth-first?

2. DFS is naturally implemented with:

3. On an unweighted graph, BFS from a source finds:

4. Why do graph traversals need a visited set?

DFS gives us a powerful tool for ordering work with dependencies. Next up: Module 25 — Topological Sort & Cycle Detection.