Breadth-First Search

Explore a graph level by level using a queue; finds shortest paths in unweighted graphs.

Intermediate

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

Runs in $O(V + E)$ . Used for shortest paths in grids and mazes, network broadcast and finding connected components.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)