BFS — Breadth-First Search

Explore a graph level by level

Use arrow keys or buttons to navigate • 24 slides

What is BFS?

Breadth-First Search starts at a source vertex and explores in expanding rings:

First, visit all neighbors of source (distance 1)
Then all neighbors of neighbors (distance 2)
Then distance 3, 4, 5… until everything reachable is explored

Analogy: Ripples in a Pond

Drop a stone into still water. Ripples expand outward in concentric circles. BFS radiates outward, reaching everything at distance k before anything at k+1.

Key Idea

BFS guarantees that when you first reach a vertex, you’ve found the shortest path (in edge count) from the source.

Try it: Click any node as the source, then watch BFS expand.

        Click a node to set it as source
      

BFS Uses a Queue

Two Key Data Structures

Queue (FIFO) — holds vertices waiting to be explored. First in, first out ensures level-by-level order.
Visited set — prevents revisiting and infinite loops in cyclic graphs.

Why a Queue?

A queue processes vertices in discovery order. All level-1 vertices enqueued before any level-2, so level-1 is fully processed first. That’s what makes it “breadth-first.”

Stack ≠ BFS

Replace the queue with a stack → you get DFS (goes deep before wide). The data structure is the fundamental difference.

        Watch how Queue (BFS) vs Stack (DFS) produce different visit orders
      

BFS Algorithm — Detailed

          BFS(graph, source):
            for each vertex v:
              dist[v] = ∞, parent[v] = null
              color[v] = WHITE
           
            dist[source] = 0
            color[source] = GRAY
            Q.enqueue(source)
           
            while Q is not empty:
              u = Q.dequeue()
              for each neighbor v of u:
                if color[v] == WHITE:
                  color[v] = GRAY
                  dist[v] = dist[u] + 1
                  parent[v] = u
                  Q.enqueue(v)
              color[u] = BLACK
        

Color Scheme (CLRS)

Color	Meaning
WHITE	Undiscovered
GRAY	Discovered, in queue
BLACK	Fully explored (dequeued)

        Step through BFS with color tracking & code sync
      

BFS Step-by-Step: Full Example

Queue: [ ]

Visited: { }

        Source = A. Step through to see queue, visited, dist, and parent evolve.
      

The BFS Tree

What Is the BFS Tree?

Each vertex (except source) is discovered from exactly one vertex. That edge is a tree edge. All tree edges form a spanning tree — the BFS tree.

Edge Classification

Type	Definition
Tree edge	Used to discover a new vertex
Cross edge	Connects same/adjacent levels, not used for discovery

Key Idea

The BFS tree encodes shortest paths. The path from any vertex back to the root in the BFS tree IS the shortest path in the original graph.

Important Property

In undirected BFS, cross edges only connect vertices whose levels differ by at most 1. No edges skip levels.

BFS Finds Shortest Paths (Unweighted)

        Click two nodes: source and destination. BFS finds the shortest path.
      

The Guarantee

In an unweighted graph (all edges cost 1), BFS discovers every vertex at the minimum distance from the source.

Why Does This Work?

BFS processes vertices in non-decreasing distance order
When we discover v from u: dist[v] = dist[u] + 1
Since u was dequeued first, dist[u] is already optimal
Therefore dist[v] is also optimal

Only Unweighted Graphs!

BFS does NOT find shortest paths in weighted graphs. Use Dijkstra’s (non-negative weights) or Bellman-Ford (negative weights).

Computing Distances

dist[v] = dist[u] + 1 when discovering v from u

        Watch the dist[] array evolve as BFS discovers vertices
      

Key Idea

Distances are computed when discovered (enqueued), not when processed (dequeued). Each vertex’s distance is set exactly once and never changes.

Reconstructing the Shortest Path

Follow the parent pointers back to the source

        Click any node to trace parent pointers back to source A
      

Parent Array (source = A)

Vertex	A	B	C	D	E	F	G	H
parent	—	A	A	B	B	C	C	D

          shortestPath(source, dest, parent):
            path = []
            current = dest
            while current != null:
              path.addFirst(current)
              current = parent[current]
            return path
        

Analogy: Breadcrumb Trail

Each vertex remembers who led it there. Follow the breadcrumbs back to find the shortest route to the source!

BFS on Directed Graphs

Same algorithm, but only follow outgoing edges

        BFS from A — only follows outgoing arrows
      

Queue: [ ]

Direction Matters!

Edge A→B does NOT mean you can go B→A. BFS only follows outgoing edges from the current vertex.

Key Idea

In directed graphs, BFS might not reach all vertices from a single source. Unreachable vertices keep dist = ∞.

BFS for Connected Components

        Each BFS call explores one entire connected component
      

Algorithm

          findComponents(graph):
            components = 0
            visited = empty set
            for each vertex v:
              if v not in visited:
                components += 1
                BFS(graph, v, visited)
            return components
        

Analogy: Islands

Each component is an island. BFS explores one island completely. You need a new “boat trip” (new BFS) to reach each separate island.

Key Idea

A single BFS explores only its connected component. Loop through all vertices and start a new BFS for each unvisited one.

Time Complexity: O(V + E)

Why O(V + E)?

          while Q not empty:        // V times
            u = Q.dequeue()         //   O(1)
            for each neighbor of u:  //   deg(u)
              if not visited:        //   O(1)
                ...                  //   O(1)
           
          Total inner loop: Σ deg(u) = 2|E|
          Total: V dequeues + O(E) checks
               = O(V + E)
        

        Dequeues: 0   Neighbor checks: 0   Total: 0
      

Why V + E, not V × E?

Each vertex dequeued once. Each edge checked once per endpoint. Work is distributed, not repeated.

Representation	BFS Time
Adjacency List	O(V + E)
Adjacency Matrix	O(V²)

Space Complexity: O(V)

Space Breakdown

Structure	Space	Purpose
Queue	O(V)	At most V vertices
visited[]	O(V)	One bool per vertex
dist[]	O(V)	One int per vertex
parent[]	O(V)	One ptr per vertex
Total	O(V)

Worst Case Queue Size

Star graph: center connects to all V-1 vertices. After dequeuing center, all V-1 neighbors are in the queue simultaneously!

Queue Size Over Time

Application: Social Network Distance

"Six degrees of separation" — BFS finds the shortest friendship chain

Click any person as source, then click another as target to find the shortest friendship chain.

Click a person to start...

Six Degrees of Separation

Any two people on Earth are connected by at most 6 friendship links. Facebook's 2016 study found the average distance is only 3.57 among 1.59 billion users.

Key Idea

BFS naturally computes the "degree of separation" — it's the foundation for LinkedIn's "2nd connection" and Facebook's "mutual friends."

Applications: Web Crawling & Maze Solving

BFS is everywhere

Why BFS for Mazes?

BFS explores cells level by level — the first time it reaches the exit is guaranteed to be the shortest path. Like flooding the maze with water from the start.

Challenge: Predict the BFS Order

Given this graph and source A, what order does BFS visit vertices?

Neighbors processed in alphabetical order. Source = A.

Type the BFS visit order (comma-separated):

Challenge: Fix the Bug

This BFS code has a subtle bug — can you find it?

BFS(graph, source):
  Q = new Queue()
  Q.enqueue(source)
  
  while Q is not empty:
    u = Q.dequeue()
    visited[u] = true  // BUG!
    for each neighbor v of u:
      if not visited[v]:
        Q.enqueue(v)

The highlighted lines mark visited when dequeuing. What goes wrong?

What's the problem with marking visited on dequeue?

Challenge: BFS or DFS?

Pick the right algorithm for each scenario

1. Find the shortest route between two subway stations (unweighted edges).

2. Detect if a dependency graph has a cycle (circular dependency).

3. Crawl a website discovering all pages close to the homepage first.

4. Generate a random maze by carving paths through a grid.

Summary & Cheat Sheet

Everything you need to know about BFS

Key Takeaways

BFS uses a queue (FIFO) to explore level by level
Finds shortest paths in unweighted graphs
Mark visited when enqueuing, not dequeuing
BFS tree gives shortest paths via parent pointers
Time: O(V + E) — linear in graph size
Space: O(V) — queue + visited + dist + parent

Common Pitfalls

Forgetting to mark source as visited before the loop
Marking visited on dequeue → duplicates in queue
Using BFS on weighted graphs (use Dijkstra instead!)

BFS vs DFS

Use BFS When...	Use DFS When...
Shortest path (unweighted)	Topological sort
Level-order traversal	Cycle detection
Nearest neighbor search	Path existence
Web crawling (breadth)	Maze generation

Quiz: Test Your BFS Knowledge

3 questions — check your answers when ready

Q1: Time complexity of BFS with adjacency list?

O(V) O(V + E) O(V²) O(E log V)

Q2: When should you mark a vertex as visited?

When dequeuing it When enqueuing it After processing all neighbors It doesn't matter

Q3: BFS guarantees shortest path in...

All graphs Weighted graphs only Unweighted graphs only Directed graphs only

Trace: BFS on a Directed Graph

Step through BFS on this directed graph starting from vertex A

Distance table:

Notice

In directed graphs, BFS only follows outgoing edges. Some vertices may be unreachable from the source — their distance stays ∞.

Predict the Output

What does this Java BFS code print?

// Graph: 0→1, 0→2, 1→3, 2→3, 3→4
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[5];
int[] dist = new int[5];
Arrays.fill(dist, -1);
 
q.add(0); visited[0] = true; dist[0] = 0;
 
while (!q.isEmpty()) {
  int u = q.poll();
  System.out.print(u + " ");
  for (int v : adj[u]) {
    if (!visited[v]) {
      visited[v] = true;
      dist[v] = dist[u] + 1;
      q.add(v);
    }
  }
}
System.out.println();
System.out.println(Arrays.toString(dist));

What is printed on the first line (visit order)?

What is the dist array output?

BFS — Breadth-First Search

What is BFS?

Analogy: Ripples in a Pond

Key Idea

BFS Uses a Queue

Two Key Data Structures

Why a Queue?

Stack ≠ BFS

BFS Algorithm — Detailed

Color Scheme (CLRS)

BFS Step-by-Step: Full Example

The BFS Tree

What Is the BFS Tree?

Edge Classification

Key Idea

Important Property

BFS Finds Shortest Paths (Unweighted)

The Guarantee

Why Does This Work?

Only Unweighted Graphs!

Computing Distances

Key Idea

Reconstructing the Shortest Path

Parent Array (source = A)

Analogy: Breadcrumb Trail

BFS on Directed Graphs

Direction Matters!

Key Idea

BFS for Connected Components

Algorithm

Analogy: Islands

Key Idea

Time Complexity: O(V + E)

Why O(V + E)?

Why V + E, not V × E?

Space Complexity: O(V)

Space Breakdown

Worst Case Queue Size

Queue Size Over Time

Application: Social Network Distance

Six Degrees of Separation

Key Idea

Applications: Web Crawling & Maze Solving

Why BFS for Mazes?

Why BFS for Web Crawling?

Challenge: Predict the BFS Order

Challenge: Fix the Bug

The Fix

Challenge: BFS or DFS?

Summary & Cheat Sheet

Key Takeaways

Common Pitfalls

BFS vs DFS

Quiz: Test Your BFS Knowledge

Trace: BFS on a Directed Graph

Notice

Predict the Output