Algorithm Guidecomplexity: O(V+E)

Breadth-First Search (BFS)

A graph traversal that uses a FIFO queue to expand the nearest nodes first, level by level. It guarantees the shortest path in unweighted graphs and underpins shortest-distance problems, connected-component detection, and topological sorting.

01Breadth-First Search (BFS)

Explore How It Works

Starting BFS. Using a FIFO queue, expand the nearest nodes layer by layer to find the shortest path to the target G.

Dequeue A and expand it. Add neighbors B, C to the back of the queue and mark them visited.

Dequeue B and expand it. Add neighbors D, E to the queue (A is already visited, so skip it).

Dequeue C and expand it. Add neighbors F, G to the queue. G is the target, but BFS checks on dequeue, so enqueue it for now.

Dequeue D. It's a leaf node with no neighbors to add. Mark it visited and move to the next node.

Dequeue E and expand it. Add neighbor H to the queue.

Dequeue F. Neighbor H is already in the queue, so skip it.

Dequeue G. It matches the target — BFS reached it via the shortest path A → C → G (depth 2).

Search complete · shortest path A → C → G (cost 2). 7 nodes explored — BFS guarantees the shortest path on an unweighted graph.

Live Python

1def bfs(graph, start, target):

# queue = [A]

2 queue = deque([start])

3 parent = {start: None}

# visited = {A}

4 visited = {start}

5 while queue:

6 current = queue.popleft()

7 for nb in graph[current]:

8 if nb not in visited:

9 visited.add(nb)

10 parent[nb] = current

11 if nb == target:

12 return reconstruct(parent, target)

13 queue.append(nb)

14 return None

1 / 9

02 Understand It Simply

For Everyone

🔑How It Works

Visits vertices level by level, nearest first. With unweighted edges that order is itself the shortest path.

💡In Plain Words

Visits the nearest nodes level by level using a queue.

Guarantees the shortest path in unweighted graphs.

📍Where It's Used

–Shortest path (unweighted)
–friend suggestions
–maze shortest distance

03 Python Implementation

A clean, readable reference implementation of the core logic of Breadth-First Search (BFS).

core_implementation.py

from collections import deque

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