## 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]:
if parent[v] is None:
parent[v] = u
level.append(v)
levels.append(level)
return parents