Обход графа: BFS и DFS

Способы представления графа, обход в ширину и в глубину, поиск кратчайшего пути в невзвешенном графе, проверка связности и циклов.

Как хранить граф

# список смежности
g = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4],
}

BFS — обход в ширину

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

from collections import deque

def bfs(g, start):
    visited = {start}
    dist = {start: 0}
    q = deque([start])
    while q:
        v = q.popleft()
        for u in g[v]:
            if u not in visited:
                visited.add(u)
                dist[u] = dist[v] + 1
                q.append(u)
    return dist   # расстояния в рёбрах от start

DFS — обход в глубину

Идём вглубь до упора, затем откатываемся. Реализуется рекурсией или стеком. Используется для поиска компонент связности, топологической сортировки, поиска циклов.

def dfs(g, v, visited=None):
    if visited is None:
        visited = set()
    visited.add(v)
    for u in g[v]:
        if u not in visited:
            dfs(g, u, visited)
    return visited

# итеративная версия — не переполняет стек на больших графах
def dfs_iter(g, start):
    visited, stack = set(), [start]
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        stack.extend(u for u in g[v] if u not in visited)
    return visited

Типовые задачи на основе обходов

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

Сложность

Оба обхода — O(n + m) на списках смежности и O(n²) на матрице смежности, где n — вершины, m — рёбра. Каждая вершина и каждое ребро обрабатываются один раз.