# Breadth First Search

## 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)
```