Breadth First Search

How does it work?

• Take a node:
• Add each adjacent to a queue
• going through the queue, visit, add each of the neighbors to queue

BFS(s, adj):
level = {s:none}
parent = {s:none}
i = 1
frontiner = [s]
while frontier:
  next = []
  for u in frontier:
    for v in Adj[u]:
      if v not in level:
        level[v] = i
        parent[v] = u
        next.append[v]
frontier = next
i += 1