Python: обход графа в ширину (BFS)

BFS (Breadth-First Search) посещает вершины по «слоям» — сначала всех соседей старта, затем соседей соседей и т.д. Структура данных — очередь (FIFO).

from collections import deque

def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for neighbor in graph[v]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

g = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"],
}
print(bfs(g, "A"))  # ['A', 'B', 'C', 'D', 'E', 'F']

deque.popleft() работает за $O(1)$ (у обычного списка — $O(n)$). BFS находит кратчайший путь в невзвешенном графе. Сложность: $O(V + E)$.