breadth-first search (BFS)

Breadth-first search (BFS) is an algorithm for traversing a graph that explores it level by level, visiting every vertex at the current distance from the starting point before moving on to vertices one step farther away.

The traversal begins at a source vertex, or node, and uses a queue to decide what to visit next. It repeatedly removes the vertex at the front of the queue and adds that vertex’s undiscovered neighbors to the back. Marking each vertex as visited when it’s first seen keeps the search from looping over a cycle or revisiting a shared neighbor.

Because it fans out one ring at a time, BFS reaches every vertex by a path with the fewest possible edges. On an unweighted graph, that makes it a standard way to find the shortest path between two vertices. With an adjacency list, where each vertex keeps a list of its neighbors, it runs in O(V + E) time for a graph of V vertices and E edges, because each vertex and edge is examined once.

Step through the traversal below to watch the search expand outward from the source: each step takes the vertex at the front of the queue, adds its undiscovered neighbors to the back, and labels every vertex with its distance from the source.

Its counterpart, depth-first search, instead follows a single path as far as it can before backtracking. BFS underlies shortest-path routing on unweighted grids and mazes, web crawlers that expand outward from a seed page, and the degrees of separation between people in a social network. On a binary tree, the same level-by-level order produces a level-order traversal.

Related Resources

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources:

• Python's deque: Implement Efficient Queues and Stacks (Tutorial)
• Python Stacks, Queues, and Priority Queues in Practice (Tutorial)
• Stacks and Queues: Selecting the Ideal Data Structure (Course)
• The Python heapq Module: Using Heaps and Priority Queues (Tutorial)
• Mazes in Python: Build, Visualize, Store, and Solve (Course)
• Python Stacks, Queues, and Priority Queues in Practice (Quiz)