Breadth-First Search (BFS): Level-by-Level Traversal and Unweighted Shortest Paths

iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more

Breadth-first search (BFS) explores a graph outward from one or more starting vertices, finishing one distance layer before moving to the next. A FIFO queue controls the order, while a visited set prevents duplicate work. In an unweighted graph, the first time BFS discovers a vertex it has found a path using the fewest possible edges. BFS does not minimize total cost when edges have different weights; use a weighted shortest-path algorithm instead.

What is breadth-first search?

BFS is a graph-traversal algorithm for visiting vertices in nondecreasing distance from a starting vertex. Distance means the number of edges on a path: the source is distance 0, its immediate neighbors are distance 1, their newly discovered neighbors are distance 2, and so on. The vertices at one distance form a layer or frontier.

#	Preview	Product	Price
1		Introduction to Algorithms, fourth edition	$99.47	Buy on Amazon
2		Algorithms (4th Edition)	$68.77	Buy on Amazon
3		Introduction to Algorithms, 3rd Edition	$90.43	Buy on Amazon
4		Algorithms	$95.41	Buy on Amazon
5		Algorithm Design	$223.83	Buy on Amazon

The algorithm is useful when you need to visit everything reachable from a source, compute the minimum number of hops in an unweighted network, test reachability, build a traversal tree, or process work in expanding waves. NetworkX groups BFS operations under its traversal APIs, including layers, edges, predecessors, successors, and trees: NetworkX traversal documentation.

BFS is not the same as depth-first search. DFS follows one branch as far as it can before backtracking; BFS exhausts the current distance layer first. That ordering is the property that gives BFS its hop-count shortest-path guarantee.

#1 Best Overall

Sale

Introduction to Algorithms, fourth edition

• color: White
• INTRODUCTION TO ALGORITHMS, FOURTH EDITION

$99.47

Buy on Amazon

How the queue-and-visited mechanism works

Initialize the source

Put the source vertex in a FIFO queue and mark it visited immediately. Marking at discovery time, rather than when removing a vertex from the queue, ensures that each vertex is enqueued at most once even when several parents point to it. If paths are required, store the source’s predecessor as empty (or use a separate marker) and set a distance of zero.

Expand the oldest queued vertex

Remove the queue’s front vertex, inspect its permitted neighbors, and handle each neighbor that is not yet visited. Mark that neighbor at once, record its predecessor as the current vertex, assign its distance as the current distance plus one, and append it to the queue’s back. Already visited neighbors are ignored for node discovery.

Stop at the right time

For a complete traversal or distances to every reachable vertex, continue until the queue is empty. For one target in an unweighted graph, you may stop as soon as the target is discovered: its predecessor chain is then a shortest path in edge count. Stopping when the target is merely removed from the queue is also correct, but it can perform extra work.

queue = [source]
visited = {source}
predecessor = {source: None}
distance = {source: 0}

while queue:
    current = queue.pop(0)          # use a deque in production code
    for neighbor in graph[current]:
        if neighbor not in visited:
            visited.add(neighbor)
            predecessor[neighbor] = current
            distance[neighbor] = distance[current] + 1
            queue.append(neighbor)

The pseudocode assumes an adjacency structure in which graph[current] yields the neighbors that the traversal is allowed to follow. A production implementation should use an O(1)-front-removal queue such as a deque rather than repeatedly shifting an array.

Worked example: seeing the layers

Consider an undirected graph with edges A–B, A–C, B–D, B–E, C–F, and E–G. Starting at A, BFS discovers the layers shown below.

Rank #2

Sale

Algorithms (4th Edition)

$68.77

Buy on Amazon

If A’s adjacency list lists C before B, the visit order can be A, C, B, F, D, E, G instead. That difference is harmless: neighbor ordering can change the order within a layer and can choose a different predecessor when multiple shortest paths exist, but it cannot make a later-distance vertex appear before an undiscovered earlier-distance vertex.

To reconstruct A-to-G, follow predecessors backward from G: G ← E ← B ← A. Reverse that sequence to obtain A → B → E → G. If no predecessor exists for a requested target, the target is outside the source’s reachable region.

Why BFS finds shortest paths in an unweighted graph

When every edge has equal cost, minimizing total cost is the same as minimizing the number of edges. BFS fully processes distance d before it discovers any vertex at distance d + 1. A vertex is therefore first discovered through a path with the fewest possible edges: if a shorter path existed, its preceding vertex would have appeared in an earlier layer and would have discovered the vertex sooner.

The predecessor recorded at first discovery is enough to recover one shortest path. There may be several equally short paths; BFS returns the one selected by the graph’s neighbor iteration order. The guarantee is about path length, not a unique route.

Do not apply this reasoning to weighted edges. A path with two expensive edges can cost more than a path with three cheap edges, even though BFS prefers the two-edge route. BFS never compares accumulated weights.

Rank #3

Sale

Introduction to Algorithms, 3rd Edition

• Hard Cover

$90.43

Buy on Amazon

Time and space complexity

For an adjacency-list graph, NetworkX classifies single-source BFS as an unweighted shortest-path method with typical time complexity O(V + E), where V is the number of vertices and E is the number of edges: NetworkX shortest-path documentation. Each reachable vertex is discovered once, and each relevant adjacency entry is examined. For an undirected graph, the two directions of an edge may both be inspected, which remains linear in V + E.

The O(V + E) figure is a documented complexity classification, not a benchmark prediction. Constant factors depend on the language, graph representation, queue implementation, and memory behavior.

Can BFS be used on weighted graphs?

Only when the weights do not change the decision—most commonly when every edge has the same weight and can be treated as unweighted. It is not a general minimum-total-weight algorithm. The NetworkX shortest-path comparison identifies these typical choices:

These are the documentation’s typical comparisons, not measured performance results. If a problem says “fewest transfers,” “minimum hops,” or “minimum number of links,” BFS fits. If it says “lowest price,” “shortest travel time,” or supplies unequal costs, select an algorithm that accumulates and compares weights.

Directed graphs: follow the permitted direction

In a directed graph, an outgoing edge from u to v allows BFS to move from u to v; the reverse move is not implied. A source may therefore reach a much smaller region than it would in an undirected interpretation. Follow the graph library’s orientation rules, and only reverse or ignore direction when the application explicitly calls for it.

Rank #4

Algorithms

$95.41

Buy on Amazon

The predecessor tree contains the directed discovery edges that connect each reached vertex back toward the source. An edge that points to an already visited vertex can still be meaningful in the original graph—it may represent a cross-edge or cycle—but it is not a new BFS-tree edge.

Node traversal versus edge traversal in NetworkX

NetworkX exposes several related operations, and their outputs are not interchangeable. bfs_edges reports the edges selected for the search tree, so each newly discovered vertex contributes its parent edge. By contrast, edge_bfs continues reporting graph edges even when an edge leads to a vertex that has already been explored. Its documentation also describes orientation choices for directed graphs: NetworkX edge_bfs documentation.

Choose a node-oriented traversal when you need reachable vertices, layers, distances, or a predecessor tree. Choose an edge-oriented report when you need to inspect the order in which graph edges are encountered, including edges that do not add a new vertex to the tree. The lower-level breadth-first implementation and its layer-related behavior are documented in NetworkX 3.2: breadth_first_search source documentation.

Disconnected graphs and multi-source BFS

One source in a disconnected graph

A normal source-based BFS stops when its queue is empty. At that point it has visited exactly the source’s reachable component, not necessarily every vertex in the graph. To traverse all components, iterate through the vertex set and start a fresh BFS from each vertex that is still unvisited. The resulting collection of trees is a BFS forest.

Several sources at once

For a multi-source search, initialize the queue with every source and mark all of them visited before processing begins. Give each source distance zero and no predecessor. The waves then expand simultaneously, assigning every reachable vertex to the nearest source in edge count. If two sources are equally close, the chosen source and predecessor depend on the order in which the initial queue and neighbors are processed.

Best Value

Sale

Algorithm Design

• Used Book in Good Condition

$223.83

Buy on Amazon

Multi-source BFS is useful for “nearest facility,” distance-to-nearest-boundary, or spreading simulations in unweighted networks. It remains a hop-count algorithm; unequal costs still require a weighted method.

A practical implementation pattern

The following Python-shaped pattern emphasizes the decisions that matter. It assumes graph maps each vertex to an iterable of neighbors and returns either a reconstructed path or None. Replace the list with collections.deque in real code so removing the front is constant time.

from collections import deque

def shortest_unweighted_path(graph, source, target):
    queue = deque([source])
    seen = {source}
    parent = {source: None}

    while queue:
        node = queue.popleft()
        if node == target:
            break
        for neighbor in graph.get(node, ()):
            if neighbor in seen:
                continue
            seen.add(neighbor)
            parent[neighbor] = node
            queue.append(neighbor)

    if target not in seen:
        return None

    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    path.reverse()
    return path

For a full traversal, remove the target check and return the visited, distance, or predecessor structures after the queue empties. For a directed graph, make sure each adjacency iterable contains only outgoing neighbors. For an undirected graph represented manually, insert both directions when constructing the adjacency map.

Common mistakes and how to correct them

• Marking vertices too late: If you wait until dequeue time, multiple parents can enqueue the same vertex repeatedly. Mark it when discovered.
• Using a stack: A stack changes the algorithm into depth-first behavior. Use FIFO semantics: append at the back and remove from the front.
• Stopping on dequeue without understanding the goal: Dequeue stopping is correct for a target, but discovery stopping avoids unnecessary work. For all distances, do not stop early.
• Forgetting unreachable targets: An empty queue with the target absent from the visited set means no path exists from that source.
• Treating edge order as canonical: Different adjacency orders can produce different, equally short paths. Test path length and validity rather than one exact predecessor tree unless ordering is specified.
• Applying BFS to costs: Convert the problem to equal-cost hops only when that is legitimate; otherwise use Dijkstra or Bellman–Ford according to the edge-weight rules.
• Ignoring graph direction: In directed data, accidentally adding reverse edges can report paths that the original graph does not permit.
• Scanning every component unintentionally: A single source does not cover disconnected vertices. Add an outer loop for a full-graph traversal.

Choosing BFS for a problem

1. Identify what a path cost means. If every step costs one and the objective is fewest steps, continue with BFS.
2. Choose the starting frontier: one source, or several sources initialized together.
3. Decide the output: reachable nodes, layer numbers, distances, predecessor links, a tree, or a particular target path.
4. Use a FIFO queue and mark vertices at discovery. Record predecessors only if reconstruction or a tree is needed.
5. For a target query, stop on discovery; for complete distances or traversal, run until the queue is empty.
6. Check direction and disconnected components before interpreting the result.
7. If edge weights affect the answer, switch to a weighted shortest-path algorithm rather than trying to modify BFS informally.

Further reading

For a broader treatment of graph representations and shortest-path algorithms, see Introduction to Algorithms, fourth edition from The MIT Press. It is a general algorithms textbook; the publisher describes it as covering algorithms with readable pseudocode.

Quick Recap

SaleBestseller No. 1

Introduction to Algorithms, fourth edition

color: White; INTRODUCTION TO ALGORITHMS, FOURTH EDITION

$99.47

SaleBestseller No. 2

Algorithms (4th Edition)

$68.77

SaleBestseller No. 3

Introduction to Algorithms, 3rd Edition

Hard Cover

$90.43

Bestseller No. 4

Algorithms

$95.41

SaleBestseller No. 5

Algorithm Design

Used Book in Good Condition

$223.83

Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.