BFS

Problem¶

List node's values in a graph starting from start node using BFS.

Key trick¶

First time you reach a node in unweighted graph gives shortest path length.

Trap¶

Mark visited when enqueuing, not when dequeuing, to avoid duplicates.

Why is it interesting?¶

BFS give you shortest path in unweighted graphs, level order and nearest target.

Python solution¶

from collections import deque

def bfs(graph, start):
    visited = {start}
    res = []
    q = deque([start])

    while q:
        node = q.popleft()
        res.append(node)
        for nei in graph.get(node, []):
            if nei not in visited:
                visited.add(nei)
                q.append(nei)

    return res