Begin Algo
Graph Algorithms · 01 / 11

BFSBreadth-first search

Spreads outward one ring at a time; made for shortest paths on unweighted graphs.

Used for: Fewest steps, degrees of separation, crawling level by level

Time complexityO(V+E)
Space complexityO(V)
DifficultyIntro
PrerequisitesQueues, adjacency lists

01Why it exists

"People you may know"

Facebook and LinkedIn suggest friends-of-friends. One hop out is your friends, two hops is their friends, and past three hops the suggestions stop being useful.

Why this fitsBFS is the only traversal that naturally works outward one ring at a time. It finishes every node at distance 1 before touching distance 2, so you get exact control over degrees of separation.

Fewest moves through a maze or map

A robot vacuum has to get from its dock to the kitchen, and every step on the grid costs the same. NPC pathfinding and "fewest transfers" transit routing are the same problem.

Why this fitsWhen every edge costs the same, the first time BFS reaches a node it has taken the fewest possible steps. You do not need anything as involved as Dijkstra.

Web crawlers and things that spread

A search engine starts at a homepage, follows every link on it, then follows the links on those pages. Epidemic models and network broadcasts spread the same way.

Why this fitsGoing near-before-far means the crawler covers the pages closest to the entry point first — usually the important ones — and you can stop cleanly at a maximum depth.

Reach for it when you see:Fewest steps, shortest path with no weights, levels or degrees of separation, nearest to a given point, spreading outward in rings.

02The core idea

BFS starts at one node and finishes everything at distance 1 before it looks at distance 2, spreading outward like a ripple. What makes the rings possible is the queue it keeps of nodes waiting to be processed: whatever was discovered first is processed first.

That property gives BFS its most useful guarantee. On an unweighted graph, the moment BFS first reaches a node, the number of edges it walked is the shortest distance from the start.

03The algorithm

  1. 1Put the start node in the queue and mark it discovered, so it is never queued twice.
  2. 2Take a node u off the front of the queue.
  3. 3For each neighbour v of u: if v is not discovered yet, mark it, record dist[v] = dist[u] + 1, and push it onto the back of the queue.
  4. 4Repeat steps 2–3 until the queue is empty. Every node reachable from the start has now been visited.

04Interactive demo

Starting from node A. Press "Next" to watch the queue advance one ring at a time; the number under each node is its distance from A.

UndiscoveredIn the queueProcessingDone
Ad=0BCDEFGH
Queue (front → back)
A
Visit order
A
Step 0/9Put the start node A in the queue, with dist[A] = 0.

05Code

Both versions let a single dist table do double duty: whether a node was discovered, and how far away it is.

from collections import deque

def bfs(adj, start):
    # adj: dict[node, list[node]]. Returns each node's distance from start.
    dist = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()          # take from the front
        for v in adj[u]:
            if v not in dist:        # not discovered yet
                dist[v] = dist[u] + 1
                queue.append(v)      # push to the back
    return dist

06Practice

  • LeetCode 1091Shortest Path in Binary MatrixMedium
  • LeetCode 994Rotting OrangesMedium
  • LeetCode 127Word LadderMedium
  • LeetCode 200Number of IslandsMedium
Previous—NextDFS