Breadth-First Search, step by step.

Breadth-first search (BFS) is a graph traversal algorithm that visits the start vertex, then all its neighbors, then all of theirs, level by level, without visiting any vertex twice, until it has visited every vertex it can reach. It keeps the vertices waiting their turn in a queue and takes O(V + E) time with an adjacency list and O(V²) with an adjacency matrix. This page explains how it works, with a step-by-step animation of BFS on a tree from the VisiGrab app.

How breadth-first search works

Breadth-first search (BFS) is a graph traversal algorithm: from a start vertex, it visits every vertex it can reach, level by level. First come the start's neighbors, the vertices joined to it by an edge, then their unvisited neighbors, and so on, the nearest first. A queue keeps the vertices waiting their turn. BFS takes O(V + E) time with an adjacency list and O(V2) with an adjacency matrix, for V vertices and E edges.

How the BFS algorithm works: queue, levels, visited marks

BFS marks each vertex visited as soon as it finds it, so no vertex is visited twice. Visited vertices wait in a queue, first in, first out: enqueue adds a vertex at the rear, and dequeue removes the one at the front, which has waited longest. The app finds neighbors in the adjacency matrix: row A has a 1 in the column of each vertex joined to A. BFS visits and enqueues the start vertex, A, then repeats two steps, shown on the app's default graph.

1. Dequeue: remove the front vertex from the queue.

2. Visit its neighbors: scan the dequeued vertex's row from the left for the first 1 in an unvisited vertex's column. Visit that neighbor, enqueue it and scan the row again. The app marks a visited vertex's column in every row, so no later scan stops there. When a scan finds nothing, go back to step 1. Row A finds B, then E, then nothing.

The steps repeat until the queue is empty. As the queue is first in, first out, vertices leave it in the order they were visited: A, then every vertex one edge away, then every vertex two edges away. These rings are the levels.

A vertex is marked when it is enqueued, not when it is dequeued. If a loop over all neighbors marked vertices only on dequeue, both B and C would enqueue D on the diamond A–B, A–C, B–D, C–D. D's first copy still leaves first, so the visit order stays the same, but the copies cost time and memory.

BFS pseudocode: iterative, not recursive

The app runs BFS as a loop over a queue. In pseudocode, with names from the app's code, from a vertex start:

queue = empty queue
visit(start)
queue.enqueue(start)
while queue is not empty
    u = queue.dequeue()
    v = findUnvisitedNeighbor(u)
    while v is not none
        visit(v)
        queue.enqueue(v)
        v = findUnvisitedNeighbor(u)

findUnvisitedNeighbor(u)
    for v from 0 to V - 1
        if matrix[u][v] == 1
            if v is not visited
                return v
    return none

Vertices are numbered from 0. visit marks a vertex as visited and always comes just before enqueue. findUnvisitedNeighbor(u), the same as in DFS, scans row u from column 0 and returns the first v with matrix[u][v] == 1 that is not visited, or none. The inner while calls it until it returns none, so neighbors join the queue lowest index first. Each dequeue and each visit after the first is followed by one scan: 2V − 1 scans when every vertex can be reached.

BFS has no natural recursive version: the call stack is last in, first out, so recursion can replace the stack of DFS but not a queue.

BFS example: a tree

The player below runs BFS from A on the app's default graph, a tree, with the queue and the adjacency matrix beside it. It visits A, then B and E, then C and F, then D, one level at a time. The dotted line leads from each visited vertex to the next one visited, so only its first segment, A to B, lies on an edge.

BFS on a tree

All steps as text
  1. Perform BFS traversal for the given graph, starting from vertex A. A dotted line leads from each visited vertex to the next one visited.
  2. Visit vertex A and enqueue it.
  3. Then dequeue vertex A and check the adjacency matrix to identify its first unvisited neighbor - vertex B. This is the next vertex to visit.
  4. Visit vertex B and enqueue it. Check the adjacency matrix to find unvisited neighbors of vertex A. Vertex E is identified as the next vertex to visit.
  5. Visit vertex E and enqueue it. Since vertex A has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  6. Dequeue vertex B and check the adjacency matrix to identify its unvisited neighbor - vertex C. This is the next vertex to visit.
  7. Visit vertex C and enqueue it. Since vertex B has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  8. Dequeue vertex E and check the adjacency matrix to identify its unvisited neighbor - vertex F. This is the next vertex to visit.
  9. Visit vertex F and enqueue it. Since vertex E has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  10. Dequeue vertex C and check the adjacency matrix to identify its unvisited neighbor - vertex D. This is the next vertex to visit.
  11. Visit vertex D and enqueue it. Since vertex C has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  12. Dequeue vertex F. This vertex has no unvisited neighbors, so continue with the next one in the queue.
  13. Dequeue vertex D. Since this vertex has no unvisited neighbors and the queue is empty, all vertices have been visited. The traversal is complete.
  14. BFS visited A, B, E, C, F, D and dequeued them in the same order: six visits, six dequeues and 11 row scans that read 56 cells.
Breadth-First Search — BFS on a tree. Last step: BFS visited A, B, E, C, F, D and dequeued them in the same order: six visits, six dequeues and 11 row scans that read 56 cells.

Does BFS find the shortest path?

Yes, in an unweighted graph: BFS first reaches every vertex by a path with the fewest edges. Follow each vertex's parent, the vertex that found it, back to the start and reverse the route to get that path. In a weighted graph the fewest edges need not give the lowest total weight: use Dijkstra's algorithm for non-negative weights, or Bellman-Ford if some are negative.

BFS shortest path, levels and the BFS tree

In an unweighted graph BFS finds a shortest path, one with the fewest edges, to every vertex it reaches. The queue holds at most two consecutive levels, the nearer in front, so each vertex is first reached by a shortest route. A vertex's parent is the vertex that found it, and its distance is its parent's plus one. The parent links form the BFS tree: follow them back from a vertex and reverse them to get its path.

The visit order depends on the order of neighbors; the levels do not. On a rooted tree, BFS is level order traversal and needs no visited marks, as each node is reached only by the link from its parent.

BFS on a weighted graph: BFS vs Dijkstra

BFS counts edges, not weights: in a weighted graph, the fewest edges need not give the lowest total weight. Road maps are weighted, so GPS route planning is not plain BFS. Dijkstra's algorithm puts a priority queue ordered by distance in place of the queue and needs non-negative weights; Bellman-Ford also handles negative ones.

BFS time and space complexity: adjacency list vs matrix

Each vertex is enqueued and dequeued once, so the time goes on finding neighbors. A matrix row has V cells however few edges there are, and each of the at most 2V − 1 scans reads at most V of them: O(V2). An adjacency list holds only real neighbors. A for-each loop over the dequeued vertex's list reads each list once: O(V + E). Repeated findUnvisitedNeighbor calls restart at the front of the list after each find, which can cost O(V2) when one vertex is joined to all the others. Extra space is O(V): the visited marks and a queue of at most V vertices.

CostAdjacency listAdjacency matrix
TimeO(V + E)O(V2)
Extra spaceO(V)O(V)

BFS vs DFS: breadth-first vs depth-first search

Depth-first search follows one path as deep as it goes, with a stack where BFS has its queue. Both take the same time; use BFS for the fewest edges and for whatever lies near the start, DFS for backtracking. Full comparison →

BFS on directed and disconnected graphs

On a directed graph BFS follows the arrows only, so its distances hold one way. When the queue empties with vertices unvisited, no path leads to them from the start. In an undirected graph, one BFS finds exactly the start's connected component, and an outer loop that starts a new BFS from each vertex still unvisited finds every component.

BFS in Python, Java and C++

The app shows the iterative version in all three languages.

Note

Python's list.pop(0), used in the app's listing, shifts every remaining item, so with an adjacency list the dequeues alone can cost O(V2) when most vertices wait in the queue at once. collections.deque dequeues with popleft() in O(1).

The standard libraries have no graph BFS. NetworkX's bfs_layers and JGraphT's BreadthFirstIterator, with getDepth, also give the levels.

The full source code is on GitHub, in Python, Java and C++.

Applications of breadth-first search

  • Fewest moves: mazes, and puzzles such as word ladders, where every move costs the same.
  • Social networks: degrees of separation, and everyone within k hops.
  • Bipartite check: an edge inside one level closes an odd cycle, so the graph is not bipartite.
  • Topological sorting: Kahn's algorithm keeps a queue of the vertices with no incoming edges left.
  • Maximum flow: Edmonds–Karp finds each augmenting path with BFS.

A tree here.
Cycles in the app.

In VisiGrab, BFS runs on four example graphs with the queue and the adjacency matrix beside each, and a message for each of its 12 visits and dequeues.

Three graphs with cycles

The Examples dialog shows four thumbnails and remembers your pick. Besides this tree there are a ring of six vertices, a graph with the triangles A–B–E and D–E–F, and a fan: the path A–B–C–D–E with F joined to all five.

BFS on a graph you draw

In the Graph Constructor, place up to 12 vertices, drag edges between them and tap Apply, then flip the DFS / BFS switch to BFS and tap the start vertex. Each tap on Next visits one vertex and adds it to the traversal order, and the Matrix button shows your graph's adjacency matrix.

Theory on one page

The info dialog defines BFS as closest vertices first, counted in edges, with two pictures of a small tree: one numbered in visit order, one with the path of visitation. It ends with O(V + E) against O(V²) and three applications.

Python, Java and C++

The iterative traverse with a queue in each language, introduced as level-by-level exploration, with a note on the findUnvisitedNeighbor it shares with DFS. A link opens the full source on GitHub.

Quiz

Four questions with an explanation for every answer: the order of visits, why BFS finds the fewest edges, why it costs the same as DFS, and what an emptied queue with unvisited vertices means.

Breadth-first, twice more

Breadth-First Traversal walks a binary tree level by level, and Topological Sort (BFS) orders a directed acyclic graph with a queue of vertices that have no incoming edges left. The Graph Constructor runs that sort on your own graph too.

Search a graph
one level at a time.

Download VisiGrab to watch the queue fill and empty on four example graphs, then draw a graph of your own and run BFS from any vertex.

Breadth-first search is one of 30+ topics. See them all