Remarks

  • The breadth first search algorithm traversals tree / graph by exploring all the immediate child nodes / neighboring nodes first before moving to next depth level.
  • BFS is good for shortest path findings.
  • BFS on graph from a single source can be used to construct a shortest path tree from that source which can be used to answer many questions.

Template

Some dummy criterion and constraints.

def criterion(node, target_val=4):
    return node and node.val == target_val

def constraints(node):
    return node

Iterative implementation using queue.

def bfs(root):
    queue = deque([root])

    while queue:
        node = queue.popleft()
        if criterion(node): return node

        for child in node.childrens:
            if not constraints(child): continue
            queue.append(child)

result = bfs(root)

Construct a shortest path tree

def bfs(adj, s):
    parent = [None for v in adj]
    parent[s] = s
    levels = [[s]]
    while 0 < len(levels[-1]):
        level = []
        for u in levels[-1]:
            for v in adj[u]:
                if parent[v] is None:
                    parent[v] = u
                    level.append(v)
    	levels.append(level)
    return parents

def unweighted_shortest_path(adj, s, t):
    parents = bfs(adj, s)
    if parent[t] is None: return None
    i = t
    path = [t]
    while i != s:
        i = parent[i]
        path.append(i)
    return reversed(path)