Breadth-First Search

Category: Classical
Difficulty: Intermediate
Time Complexity: O(V + E)
Space Complexity: O(V)

Overview

BFS explores all neighbors of the current node before moving to the next level. It uses a FIFO queue and guarantees the shortest path (minimum edges) in unweighted graphs.

Try It

Web: Open in Eigenvue →
Python:
```
import eigenvue
eigenvue.show("bfs")
```

Default Inputs

{
  "adjacencyList": {
    "A": [
      "B",
      "C"
    ],
    "B": [
      "A",
      "D",
      "E"
    ],
    "C": [
      "A",
      "F"
    ],
    "D": [
      "B"
    ],
    "E": [
      "B",
      "F"
    ],
    "F": [
      "C",
      "E"
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.5
    },
    "B": {
      "x": 0.35,
      "y": 0.2
    },
    "C": {
      "x": 0.35,
      "y": 0.8
    },
    "D": {
      "x": 0.65,
      "y": 0.1
    },
    "E": {
      "x": 0.65,
      "y": 0.5
    },
    "F": {
      "x": 0.9,
      "y": 0.8
    }
  },
  "startNode": "A",
  "targetNode": "F"
}

Input Examples

6-node graph (find F)

{
  "adjacencyList": {
    "A": [
      "B",
      "C"
    ],
    "B": [
      "A",
      "D",
      "E"
    ],
    "C": [
      "A",
      "F"
    ],
    "D": [
      "B"
    ],
    "E": [
      "B",
      "F"
    ],
    "F": [
      "C",
      "E"
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.5
    },
    "B": {
      "x": 0.35,
      "y": 0.2
    },
    "C": {
      "x": 0.35,
      "y": 0.8
    },
    "D": {
      "x": 0.65,
      "y": 0.1
    },
    "E": {
      "x": 0.65,
      "y": 0.5
    },
    "F": {
      "x": 0.9,
      "y": 0.8
    }
  },
  "startNode": "A",
  "targetNode": "F"
}

Explore all (no target)

{
  "adjacencyList": {
    "A": [
      "B",
      "C"
    ],
    "B": [
      "A",
      "D"
    ],
    "C": [
      "A"
    ],
    "D": [
      "B"
    ]
  },
  "positions": {
    "A": {
      "x": 0.2,
      "y": 0.5
    },
    "B": {
      "x": 0.5,
      "y": 0.2
    },
    "C": {
      "x": 0.5,
      "y": 0.8
    },
    "D": {
      "x": 0.8,
      "y": 0.5
    }
  },
  "startNode": "A"
}

Code

Pseudocode

function BFS(graph, start, target?):
  visited = {start}
  queue = [start]
  predecessor[start] = null
  while queue is not empty:
    current = queue.dequeue()
    for each neighbor of current:
      if neighbor not in visited:
        visited.add(neighbor)
        predecessor[neighbor] = current
        queue.enqueue(neighbor)
        if neighbor == target:
          return reconstructPath(predecessor, target)
  return null  // target not found

Python

from collections import deque

def bfs(graph, start, target=None):
    visited = {start}
    queue = deque([start])
    pred = {start: None}
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                pred[neighbor] = current
                queue.append(neighbor)
                if neighbor == target:
                    return reconstruct(pred, target)
    return None

Key Concepts

Level-by-Level Exploration

BFS visits all nodes at distance d before any at distance d+1. This is guaranteed by the FIFO queue.

Shortest Path (Unweighted)

The first time BFS reaches a node, it found the shortest path (fewest edges). This does NOT apply to weighted graphs — use Dijkstra for those.

Queue (FIFO)

The queue ensures first-in-first-out order, which is what makes BFS explore level by level rather than depth-first.

Common Pitfalls

Not for weighted graphs: BFS finds the shortest path only in UNWEIGHTED graphs. For weighted graphs, use Dijkstra’s algorithm.
Memory usage: BFS can use a lot of memory because it stores all nodes at the current level in the queue. For very wide graphs, this can be a problem.

Quiz

Q1: What data structure does BFS use?

A) Stack
B) Queue
C) Priority Queue
D) Hash Set

Show answer

Answer: B) Queue

BFS uses a FIFO queue. Nodes are added to the back and removed from the front, ensuring level-by-level exploration.

Q2: Does BFS guarantee the shortest path?

A) Always
B) Only in unweighted graphs
C) Only in weighted graphs
D) Never