Breadth-First Search (BFS) Tutorial

A concise, step-by-step guide to BFS on a simple graph

What is BFS?

• Breadth-First Search (BFS) is a graph traversal algorithm.
  
• It visits all nodes at the current “depth” before moving on to nodes at the next depth level.
  
• Often implemented with a queue to track which node to visit next.

Why use BFS?

• Shortest path in unweighted graphs: Finds the minimum number of edges from a start node to every other reachable node.
  
• Layered traversal: Processes nodes level-by-level, useful for problems like finding connected components or testing bipartiteness.
  
• Guaranteed completeness: If a solution exists, BFS will find it (in finite graphs).

Real-world examples

• Social networks: Finding all friends at distance ≤ 2 from a user.
  
• Routing in networks: Computing minimum hop counts in peer-to-peer or mesh networks.
  
• Web crawlers: Discovering all pages within k clicks of a given URL.
  
• Shortest path puzzles: Solving mazes where each move costs the same.

BFS Pseudocode

BFS(Graph, start):
  let Q be a new empty queue
  mark start as “discovered” and enqueue start into Q
  while Q is not empty:
    v ← dequeue(Q)
    for each neighbor w of v:
      if w is not yet discovered:
        mark w as “discovered”
        enqueue w into Q

Example: Traversing a Simple Graph

We’ll traverse this 7-node undirected graph, starting at node A:

Queue

← Front

← Rear

Step-by-Step BFS Execution

1. Initialization
   • Queue Q = [A]
     
   • Discovered = {A}
     
   • Order = []
2. Step 1
   • Dequeue: v = A → Order = [A]
     
   • Enqueue A’s neighbors (B, C):
     • Q = [B, C]
       
     • Discovered = {A, B, C}
3. Step 2
   • Dequeue: v = B → Order = [A, B]
     
   • Enqueue B’s undiscovered neighbors (D, E):
     • Q = [C, D, E]
       
     • Discovered = {A, B, C, D, E}
4. Step 3
   • Dequeue: v = C → Order = [A, B, C]
     
   • Enqueue C’s undiscovered neighbors (F, G):
     • Q = [D, E, F, G]
       
     • Discovered = {A, B, C, D, E, F, G}
5. Step 4
   • Dequeue: v = D → Order = [A, B, C, D]
     
   • D’s neighbors (only B) already discovered → no change
     
   • Q = [E, F, G]
6. Step 5
   • Dequeue: v = E → Order = [A, B, C, D, E]
     
   • E’s neighbors (only B) already discovered → no change
     
   • Q = [F, G]
7. Step 6
   • Dequeue: v = F → Order = [A, B, C, D, E, F]
     
   • F’s neighbors (only C) already discovered → no change
     
   • Q = [G]
8. Step 7
   • Dequeue: v = G → Order = [A, B, C, D, E, F, G]
     
   • G’s neighbors (only C) already discovered → no change
     
   • Q = []

All nodes have now been visited.

Final BFS visitation order:

A → B → C → D → E → F → G

Earning Opportunity with AI

Grab Great Deals

Coursera Courses Deal    Get AppSumo Deal

Enjoyed this post?

If this article helped you,
☕ Buy me a coffee
Your support keeps more things coming!