Поиск в ширину (BFS)

BFS обходит граф по уровням: сначала все соседи стартовой вершины, затем их соседи и так далее. Использует очередь и находит кратчайший путь по числу рёбер в невзвешенном графе.

Сложность: время O(V + E); память: O(V) под очередь и множество посещённых.

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        v = q.popleft()
        order.append(v)
        for nb in graph[v]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return order