EthicsComputerCourses
Join training
  1. Tutorials
  2. Data Structures & Algorithms
  3. Graphs

Breadth-First Search (BFS)

DSA · Lesson 23 of 34 6 min read Updated

Breadth-first search (BFS) explores a graph in waves. Starting from one vertex, it first visits all its neighbours, then all their unvisited neighbours, and so on, like ripples spreading from a stone dropped in a pond. Because it moves outwards one step at a time, BFS finds the shortest path in any graph where every edge counts the same, such as the fewest metro stops or the fewest moves in a maze.

In this lesson you will write BFS with a queue, use it to measure distances, rebuild actual shortest paths, solve a grid maze and run BFS from several starting points at once.

The BFS algorithm

BFS needs two things: a queue (first in, first out, see Queues & Deques) holding vertices waiting to be explored, and a visited set so that no vertex is processed twice. The steps are:

  1. Put the start vertex in the queue and mark it visited.
  2. Take the vertex at the front of the queue.
  3. For each neighbour that is not yet visited, mark it visited and add it to the back of the queue.
  4. Repeat from step 2 until the queue is empty.

Here BFS finds the "degrees of separation" from Aarav in a friendship network: friends are at distance 1, friends of friends at distance 2, and so on.

PythonRun it yourself
from collections import deque

friends = {
    "Aarav": ["Priya", "Kabir"],
    "Priya": ["Aarav", "Meera", "Rohan"],
    "Kabir": ["Aarav", "Rohan"],
    "Meera": ["Priya", "Isha"],
    "Rohan": ["Priya", "Kabir", "Farhan"],
    "Isha": ["Meera"],
    "Farhan": ["Rohan"],
    "Ananya": [],                      # no friends in this group
}

def bfs(graph, start):
    distance = {start: 0}              # doubles as the visited set
    queue = deque([start])
    order = []
    while queue:
        person = queue.popleft()
        order.append(person)
        for friend in graph[person]:
            if friend not in distance:
                distance[friend] = distance[person] + 1
                queue.append(friend)
    return order, distance

order, distance = bfs(friends, "Aarav")
print("visit order:", order)
print(distance)
print("Ananya reachable?", "Ananya" in distance)
Output
visit order: ['Aarav', 'Priya', 'Kabir', 'Meera', 'Rohan', 'Isha', 'Farhan']
{'Aarav': 0, 'Priya': 1, 'Kabir': 1, 'Meera': 2, 'Rohan': 2, 'Isha': 3, 'Farhan': 3}
Ananya reachable? False

The visit order shows the waves: Aarav, then distance 1 (Priya, Kabir), then distance 2 (Meera, Rohan), then distance 3. Ananya never appears because no path leads to her.

Every vertex enters the queue at most once, and every edge is looked at once from each end, so BFS takes O(V + E) time and O(V) extra space.

Why does BFS give shortest distances? The queue always holds vertices of distance d, followed by vertices of distance d + 1, never anything further away. So the first time BFS reaches a vertex, it has come by a path with the fewest possible edges.

Rebuilding the shortest path

Distances tell you how far, but a route planner must say which way. Record each vertex's parent: the vertex it was discovered from. To rebuild the path, start at the target and follow parents back to the start, then reverse.

PythonRun it yourself
from collections import deque

# A small metro map: station -> neighbouring stations
metro = {
    "Rajiv Chowk": ["Barakhamba", "Patel Chowk", "Mandi House"],
    "Barakhamba": ["Rajiv Chowk", "Mandi House"],
    "Patel Chowk": ["Rajiv Chowk", "Central Secretariat"],
    "Mandi House": ["Rajiv Chowk", "Barakhamba", "Pragati Maidan", "ITO"],
    "Central Secretariat": ["Patel Chowk", "Khan Market"],
    "Khan Market": ["Central Secretariat", "JLN Stadium"],
    "Pragati Maidan": ["Mandi House", "Indraprastha"],
    "ITO": ["Mandi House", "Delhi Gate"],
    "Indraprastha": ["Pragati Maidan"],
    "Delhi Gate": ["ITO"],
    "JLN Stadium": ["Khan Market"],
}

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        station = queue.popleft()
        if station == goal:
            break                              # found: stop early
        for nxt in graph[station]:
            if nxt not in parent:
                parent[nxt] = station
                queue.append(nxt)
    if goal not in parent:
        return None
    path = []
    while goal is not None:                    # walk back to the start
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

route = shortest_path(metro, "Barakhamba", "Khan Market")
print(" -> ".join(route), f"({len(route) - 1} stops)")
print(shortest_path(metro, "Delhi Gate", "Indraprastha"))
Output
Barakhamba -> Rajiv Chowk -> Patel Chowk -> Central Secretariat -> Khan Market (4 stops)
['Delhi Gate', 'ITO', 'Mandi House', 'Pragati Maidan', 'Indraprastha']

The station names are real, but this map is simplified for the example and is not the actual metro network. Stopping as soon as the goal leaves the queue saves time when the goal is close to the start.

BFS on a grid

In Graphs & Representations you saw that a grid is a graph whose neighbours are computed on the fly. BFS on the same city map finds the shortest walk from S to E, moving up, down, left or right and never through #.

PythonRun it yourself
from collections import deque

city_map = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    "...#...E",
]
ROWS, COLS = len(city_map), len(city_map[0])

def find(ch):
    for r, row in enumerate(city_map):
        if ch in row:
            return r, row.index(ch)

def grid_bfs(start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            break
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < ROWS and 0 <= nc < COLS and city_map[nr][nc] != "#"
                    and (nr, nc) not in parent):
                parent[(nr, nc)] = (r, c)
                queue.append((nr, nc))
    path, cell = [], goal
    while cell:
        path.append(cell)
        cell = parent[cell]
    return path[::-1]

start, goal = find("S"), find("E")
path = grid_bfs(start, goal)
print("steps:", len(path) - 1)

drawing = [list(row) for row in city_map]
for r, c in path[1:-1]:
    drawing[r][c] = "*"
print("\n".join("".join(row) for row in drawing))
Output
steps: 10
S**#....
.#*#.##.
.#***#..
...#***E

The * cells mark one shortest route. There may be other routes of the same length; BFS returns the first one it finds, which depends on the order in which the four directions are checked.

Multi-source BFS

Sometimes you need the distance from every cell to the nearest of several places, such as the nearest ambulance station for each locality. Running BFS once per station is wasteful. Instead, put all stations in the queue at distance 0 before starting. The waves then spread from every station at the same time, and each cell is reached first by its nearest station.

PythonRun it yourself
from collections import deque

area = [
    "A....#..",
    ".##..#..",
    "......#A",
    "..#.....",
    "A.......",
]
ROWS, COLS = len(area), len(area[0])

dist = [[None] * COLS for _ in range(ROWS)]
queue = deque()
for r in range(ROWS):
    for c in range(COLS):
        if area[r][c] == "A":                 # every ambulance station
            dist[r][c] = 0
            queue.append((r, c))

while queue:
    r, c = queue.popleft()
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and area[nr][nc] != "#" \
                and dist[nr][nc] is None:
            dist[nr][nc] = dist[r][c] + 1
            queue.append((nr, nc))

for r in range(ROWS):
    print(" ".join("#" if area[r][c] == "#" else str(dist[r][c]) for c in range(COLS)))
Output
0 1 2 3 4 # 3 2
1 # # 4 5 # 2 1
2 3 4 5 5 4 # 0
1 2 # 4 4 3 2 1
0 1 2 3 4 4 3 2

The whole map is filled in one BFS of O(rows × columns), however many stations there are. The same trick answers "how long until every cell is reached" questions, such as news spreading from several villages at once.

Common mistakes

  • Marking a vertex visited when it is taken out of the queue instead of when it is added. The same vertex can then be added many times, wasting time and memory.
  • Using a list with pop(0) as the queue. That is O(n) per step; use collections.deque.
  • Using BFS for weighted shortest paths. BFS counts edges, not kilometres. With weights, use Dijkstra's algorithm.
  • Forgetting the bounds check on grids, which causes IndexError or, with negative indexes, silently wraps around to the other side of the grid.

Key points

  • BFS explores level by level with a FIFO queue and a visited set.
  • It runs in O(V + E) time and finds shortest paths when all edges count the same.
  • Store a parent for each discovered vertex to rebuild the actual path.
  • Grids are graphs: compute up, down, left and right neighbours and check bounds and walls.
  • Multi-source BFS starts with every source in the queue and finds the distance to the nearest one in a single pass.

Exercise

Using the metro dictionary from the shortest path example, write stations_within(graph, start, max_stops) that returns all stations reachable from start in at most max_stops stops, sorted alphabetically (do not include the start). Print the result for "Mandi House" with 1 stop and with 2 stops.

Show solution
Python
from collections import deque

metro = {
    "Rajiv Chowk": ["Barakhamba", "Patel Chowk", "Mandi House"],
    "Barakhamba": ["Rajiv Chowk", "Mandi House"],
    "Patel Chowk": ["Rajiv Chowk", "Central Secretariat"],
    "Mandi House": ["Rajiv Chowk", "Barakhamba", "Pragati Maidan", "ITO"],
    "Central Secretariat": ["Patel Chowk", "Khan Market"],
    "Khan Market": ["Central Secretariat", "JLN Stadium"],
    "Pragati Maidan": ["Mandi House", "Indraprastha"],
    "ITO": ["Mandi House", "Delhi Gate"],
    "Indraprastha": ["Pragati Maidan"],
    "Delhi Gate": ["ITO"],
    "JLN Stadium": ["Khan Market"],
}

def stations_within(graph, start, max_stops):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        s = queue.popleft()
        if dist[s] == max_stops:
            continue                        # do not go further from here
        for nxt in graph[s]:
            if nxt not in dist:
                dist[nxt] = dist[s] + 1
                queue.append(nxt)
    return sorted(s for s in dist if s != start)

print(stations_within(metro, "Mandi House", 1))
print(stations_within(metro, "Mandi House", 2))
Output
['Barakhamba', 'ITO', 'Pragati Maidan', 'Rajiv Chowk']
['Barakhamba', 'Delhi Gate', 'ITO', 'Indraprastha', 'Patel Chowk', 'Pragati Maidan', 'Rajiv Chowk']

BFS reaches vertices in order of distance, so you can simply stop expanding any station that is already max_stops away. Every station still in dist is within the limit.

Quick Quiz

1. Which data structure does BFS use to decide what to explore next?

2. What is the time complexity of BFS on a graph stored as an adjacency list?

3. When should a vertex be marked as visited in BFS?

4. For which problem is plain BFS the right tool?

Learn DSA with a mentor

Free lessons get you started. Our Java, C & C++ Programming training adds real projects and code reviews from working developers.

  • Project-based learning
  • Mentor code reviews
  • Free counselling call
Get course details +91 90532 10052