Breadth-first search (BFS) explores a graph like a wave: first the start vertex, then its neighbours, then the neighbours of the neighbours. It keeps the discovered vertices in a queue (FIFO): it takes the vertex at the front and adds its unseen neighbours to the back. So the vertices are processed in order of increasing distance from the start, and that is why BFS finds shortest paths in an unweighted graph. The code differs from DFS in one place: a queue instead of a stack.
BFS: distances and layers
The dist dictionary plays two roles: it stores the distance and tells which vertices are already seen. A vertex is marked as soon as it is put into the queue. Python's collections.deque gives O(1) operations at both ends, see the collections module.
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
from collections import deque
def bfs(graph, start):
dist = {start: 0} # also serves as "visited"
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if v not in dist:
dist[v] = dist[u] + 1 # one edge farther than u
queue.append(v)
return dist
dist = bfs(graph, "A")
print(dist)
levels = {}
for v, d in dist.items():
levels.setdefault(d, []).append(v)
print(levels)