Поиск в ширину (BFS) обходит граф волной: сначала стартовая вершина, затем её соседи, затем соседи соседей. Открытые вершины он держит в очереди (FIFO): берёт вершину из начала и добавляет её невиданных соседей в конец. Поэтому вершины обрабатываются в порядке возрастания расстояния от старта, и именно потому BFS находит кратчайшие пути в невзвешенном графе. Код отличается от DFS в одном месте: вместо стека очередь.

BFS из A: слои расстояний 0, 1, 2 и очередь
BFS из A: слои расстояний 0, 1, 2 и очередь

BFS: расстояния и слои

Словарь dist играет две роли: хранит расстояние и показывает, какие вершины уже видели. Вершина помечается сразу при добавлении в очередь. collections.deque в Python даёт операции за O(1) с обоих концов, см. тему модуль collections.

python
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)
text
{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}
{0: ['A'], 1: ['B', 'C'], 2: ['D', 'E', 'F']}