BFS

BFS, or breadth-first search, visits vertices in layers from a starting point. It processes all vertices at distance one before vertices at distance two.

BFS uses a queue to preserve discovery order.

Core Idea

The algorithm starts with one vertex, records it as visited, and places it in a queue. It repeatedly removes the oldest queued vertex and adds its unvisited neighbors.

Because of this layer order, BFS finds shortest paths in an unweighted graph.

Python Example

from collections import deque
 
def bfs(graph, start):
    visited = {start}
    queue = deque([start])
 
    while queue:
        node = queue.popleft()
        print(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

The visited set prevents repeated processing.

Common Confusions

BFS shortest path means shortest by number of edges. It does not handle different edge weights by itself.

Marking a node visited when it is enqueued avoids adding the same node many times.

When To Use It

Use BFS for level-order traversal, shortest paths in unweighted graphs, minimum moves where every move has equal cost, and finding all nodes reachable from a start.