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.
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.
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.
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.
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.
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 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.
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.
| Cost | Adjacency list | Adjacency matrix |
|---|---|---|
| Time | O(V + E) | O(V2) |
| Extra space | O(V) | O(V) |
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 →
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.
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++.
// 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.
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.
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.
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.
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.
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 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.
// build your own
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