Breadth-First Search BFS and Depth-First Search DFS: Concepts and Worked Examples | AI Research

Breadth-First Search (BFS) and Depth-First Search (DFS): Concepts and Worked Examples

Verified Sources

Nov 4, 2026

Breadth-First Search BFS and Depth-First Search DFS are two foundational strategies for exploring graphs graph.

At a high level:

BFS explores the graph in layers (all nodes at distance $k$ from the start are visited before distance $k+1$ ), which makes it ideal for finding shortest paths in unweighted graphs.
DFS explores by going deep first, which is useful for tasks like connectivity checking and cycle detection (with the right bookkeeping).

The key implementation idea is the data structure:

BFS uses a queue (FIFO) to ensure “level-order” expansion.
DFS uses a stack behavior (explicit stack or recursion) to ensure “deep-first” expansion.

Important: I attempted to run web searches to support every major claim with citations, but the web-search tool is currently unavailable due to plan/quota limits. As a result, I cannot include the required external citations/footnotes for this response.

Breadth-First Search (BFS) — step-by-step

1
Step 1
Select a source vertex $s$ . Initialize a queue with $s$ .
2
Step 2
Mark $s$ as visited, then push it into the queue.
3
Step 3
While the queue is not empty, pop the front vertex $u$ and iterate over its adjacency list.
4
Step 4
For each neighbor $v$ of $u$ , if $v$ is unvisited, mark it visited, record its parent/level if needed, and enqueue $v$ .
5
Step 5
"When the queue empties, BFS has visited the reachable component from $s$ , producing a BFS tree."

Keywords: queue, adjacency list, BFS tree.

Depth-First Search (DFS) — step-by-step

1
Step 1
Select a source vertex $s$ . Initialize an empty stack (if iterative) or start recursion at $s$ .
2
Step 2
Mark $s$ visited and push it onto the stack (iterative) or call DFS(s) (recursive).
3
Step 3
From the top of the stack (or current recursion frame), pick an unvisited neighbor $v$ .
4
Step 4
Mark $v$ visited, then either recurse into $v$ or push $v$ onto the stack.
5
Step 5
If all neighbors are visited, backtrack (return from recursion or pop the stack).
6
Step 6
"DFS ends after exploring as deep as possible along every branch in the reachable component."

Keywords: stack, backtracking, DFS tree.

Worked Example Graph

Let’s use the same undirected graph for both BFS and DFS traversals:

Vertices: $\{A,B,C,D,E,F,G\}$

Edges:
$A$ connected to $B,C$
$B$ connected to $D,E$
$C$ connected to $F$
$D$ connected to $G$
$E$ connected to $G$
$F$ connected to $E$
(Assume adjacency lists are processed in alphabetical order for determinism.)

BFS example (from $A$ )

With BFS, we visit nodes by increasing distance from $A$ :

Distance 0: $A$
Distance 1: $B, C$
Distance 2: $D, E, F$
Distance 3: $G$

One consistent BFS order (depending on adjacency iteration order) is: $A,\; B,\; C,\; D,\; E,\; F,\; G$

Why BFS yields shortest paths in unweighted graphs:
When BFS first discovers a vertex $v$ , it has found a path from $s$ using the minimum number of edges—because BFS explores all vertices at distance $k$ before any at distance $k+1$ .

DFS example (from $A$ )

With DFS (alphabetical neighbor order), DFS goes deep before backtracking:

Starting at $A$ :

Visit $A$ , then go to $B$
From $B$ , go to $D$
From $D$ , go to $G$
Backtrack; from $B$ next go to $E$
From $E$ , $G$ is already visited; backtrack
Back to $A$ , next go to $C$
From $C$ , go to $F$
From $F$ , neighbor $E$ already visited; backtrack and finish

A consistent DFS visitation order is: $A,\; B,\; D,\; G,\; E,\; C,\; F$

DFS does not guarantee shortest paths; it guarantees a systematic exploration pattern.

BFS vs DFS: traversal behavior (intuition)

Qualitative comparison for the same start node and neighbor ordering.

Visual intuition (BFS layers vs DFS deep dives)

Common pitfalls and edge cases

Pro Tip

To reconstruct an actual path with BFS, store a parent pointer when you discover each node. Then backtrack from the target to the start.

Warning: recursion depth vs iterative DFS

Recursive DFS may overflow the call stack on very large graphs or deep recursion paths. Iterative DFS using an explicit stack is safer in production systems.

How these traversals are commonly taught/used

Graph model

1. Representation

Choose adjacency list/matrix and define neighbors."

Queue (BFS) vs stack (DFS)

2. Core mechanism

Select the data structure and the visited rule."

BFS levels vs DFS discovery path

3. Interpretation

Use BFS levels for shortest paths; use DFS tree for deep structure."

Shortest paths / components / cycles

4. Applications

BFS: shortest unweighted paths; DFS: topology & cycle detection (with extra logic)."

from collections import deque

def bfs(graph, start):
    visited = set([start])
    parent = {start: None}
    q = deque([start])

    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                parent[v] = u
                q.append(v)
    return order, parent

Knowledge Check

Question 1 of 4

Q1Single choice

Which data structure is most associated with Breadth-First Search?

Queue (FIFO)

Stack (LIFO)

Priority queue

Hash table only

Note on citations

"This output could not include the mandatory external citations because the web-search tool returned quota/plan errors during research. If you enable web access, I can regenerate the section with full source-backed claims and footnotes."

Footnotes

Explore Related Topics

Link-State Routing: Principles, Mechanics, and a Worked Example

Constraint Satisfaction Problems (CSPs): Which Methods are Usually Used and Why

Web and Distributed Databases: Concepts and Worked Examples

Browse all research articles