Модель графа: список смежности и DFS для связных компонент

В Trie рекурсивный DFS шёл только по дочерним переходам: к узлу нельзя было вернуться по обратному ребру. В произвольном графе встречаются циклы и несколько путей к одной вершине, поэтому обходу нужны представление соседей и явная отметка посещённых вершин.

Список смежности: структура dict of lists для ориентированных и неориентированных графов

Граф — это множество вершин V и множество рёбер E. Вопрос только в том, как хранить эту информацию в памяти так, чтобы удобно её обходить.

Самый практичный способ — словарь, где каждому ключу-вершине соответствует список её соседей:

# Неориентированный граф: 5 вершин, рёбра (0,1), (1,2), (3,4)
adj_undirected: dict[int, list[int]] = {
    0: [1],
    1: [0, 2],
    2: [1],
    3: [4],
    4: [3],
}

# Ориентированный граф: рёбра 0→1, 1→2, 3→4
adj_directed: dict[int, list[int]] = {
    0: [1],
    1: [2],
    2: [],
    3: [4],
    4: [],
}

Вершина 2 в ориентированном графе присутствует как ключ с пустым списком, хотя у неё нет исходящих рёбер. Ключи словаря задают само множество вершин V, и изолированная или «тупиковая» вершина обязана быть представлена — иначе алгоритм обхода её просто не увидит.

Правило добавления рёбер различается для двух типов графов:

• Ориентированный: ребро u → v добавляется только в adj[u]. adj[v] не трогаем — обратного ребра нет.
• Неориентированный: ребро (u, v) добавляется в обе стороны — adj[u].append(v) и adj[v].append(u).

def add_edge_directed(adj, u, v):
    adj[u].append(v)

def add_edge_undirected(adj, u, v):
    adj[u].append(v)
    adj[v].append(u)

Ошибка «забыл добавить в обе стороны» для неориентированного графа приводит к асимметричному adj: из u виден v, но из v — нет. DFS обойдёт лишь часть компоненты и выдаст неверный результат без единого исключения.

Память. В ориентированном графе каждое ребро порождает одну запись в списках соседей, итого E записей. В неориентированном — две записи на ребро, итого 2E. В обоих случаях плюс V ключей словаря. Суммарно — O(V + E).

Для сравнения: матрица смежности хранит V × V ячеек вне зависимости от числа рёбер. При разреженном графе, где E намного меньше V², разница становится огромной. Например, для миллиона вершин матрица содержит 10¹² ячеек. Десять миллионов неориентированных рёбер дают 2 · 10⁷ записей о соседях плюс ключи вершин: это разные порядки объёма хранения.

Сравнение списка и матрицы смежности по памяти и времени обхода

Сравним представления по конкретным операциям.

Память: — матрица смежности — O(V²);

• список смежности — O(V + E).

Проверка наличия ребра (u, v):

Если вершины пронумерованы от 0 до V - 1 (или заранее сопоставлены индексам), в матрице это matrix[u][v], то есть O(1). В списке — нужно найти v среди соседей u, то есть пройти по adj[u]. В худшем случае это O(degree(u)), где degree(u) — степень вершины. Для плотного графа это может быть O(V), но в среднем гораздо меньше.

Перебор всех соседей вершины u:

В матрице — нужно пройти всю строку u от 0 до V-1 и проверить каждую ячейку: O(V). В списке — просто итерировать adj[u]: O(degree(u)). Если у вершины три соседа, список даёт три шага; матрица всё равно требует V шагов.

Суммарная стоимость DFS по всему графу:

DFS посещает каждую вершину один раз и для каждой перебирает всех её соседей. Суммарный перебор соседей — это сумма степеней по всем вершинам, что равно E (для ориентированного) или 2E (для неориентированного). Итого:

• Список смежности: O(V + E)
• Матрица смежности: O(V²) — потому что для каждой из V вершин проходим строку длиной V

При V = 10 000 и E = 50 000 величина V + E равна 60 000, а V² — 10⁸. Это сравнение порядков роста, а не точный счёт машинных операций: в неориентированном списке каждое ребро встречается дважды.

Когда матрица всё же лучше? Если нужна быстрая проверка O(1) для произвольного ребра и граф плотный (E близко к V²), матрица оправдана. Типичный пример — алгоритмы на полных или почти полных графах, где E ≈ V²/2. Тогда и память O(V²) уже не отличается от O(V + E) по порядку.

Список смежности особенно полезен при E ≪ V²: он не хранит отсутствующие рёбра. Для плотного графа асимптотический разрыв по памяти исчезает, и выбор зависит от нужных операций.

Рекурсивный DFS с множеством посещённых: корректность и сложность

Когда мы обходили бинарное дерево рекурсивно, достаточно было пройти по node.left и node.right. Граф устроен иначе: из вершины A можно добраться до B, из B — снова до A. Без дополнительного механизма рекурсия зациклится.

Обход хранит множество visited; вершину нужно отметить до перехода к соседям.

def dfs(adj: dict, node, visited: set) -> None:
    visited.add(node)          # отмечаем до перехода к соседям
    for nb in adj[node]:
        if nb not in visited:
            dfs(adj, nb, visited)

Посмотрим, что произойдёт с графом, содержащим цикл 0 — 1 — 2 — 0:

adj = {0: [1, 2], 1: [0, 2], 2: [1, 0]}

Запускаем dfs(adj, 0, set()):

• входим в 0, visited = {0}
• входим в 1 (не в visited), visited = {0, 1}
• из 1 смотрим на 0 — уже в visited, пропускаем
• входим в 2 (не в visited), visited = {0, 1, 2}
• из 2 смотрим на 1 и 0 — оба в visited, возвращаемся

Инвариант: вершина добавляется в visited до обработки её соседей. Поэтому обратное ребро или другой путь к этой вершине не запускает повторный вызов.

Что было бы, если отмечать вершину после рекурсивных вызовов? Из 1 мы бы снова вызвали dfs(adj, 0, ...), потому что 0 ещё не в visited — и получили бесконечную рекурсию.

Контракт вызова. node должен быть ключом adj, все соседи также должны присутствовать среди ключей, а внешний вызов должен начинаться с вершины, которой ещё нет в visited. Рекурсивные вызовы сохраняют последнее условие проверкой if nb not in visited.

Сложность. При этом контракте каждая достижимая вершина обрабатывается один раз. Если достижимая часть содержит V_r вершин и E_r рёбер, время работы — O(V_r + E_r), множество visited занимает O(V_r), а стек вызовов — до O(V_r). Верхняя граница по всему графу — O(V + E) по времени и O(V) по дополнительной памяти.

Ограничение глубины рекурсии. Python по умолчанию ограничивает глубину стека вызовов значением около 1000. На графе-пути из 5000 вершин глубина DFS может достичь 5000 и превысить этот лимит.

Для таких входов нужен итеративный DFS с явным стеком либо гарантированное ограничение глубины. Здесь используем рекурсивную версию, чтобы сосредоточиться на инварианте visited.

Связные компоненты неориентированного графа и достижимые вершины ориентированного

Один запуск dfs обходит только ту часть графа, которая достижима из стартовой вершины. Для неориентированного графа с несколькими изолированными частями этого недостаточно — нужно найти все компоненты связности.

Компоненты через внешний цикл. DFS запускается из каждой ещё не посещённой вершины. Одно множество visited используется во всех запусках.

def dfs_collect(adj: dict, node, visited: set, component: list) -> None:
    visited.add(node)
    component.append(node)
    for nb in adj[node]:
        if nb not in visited:
            dfs_collect(adj, nb, visited, component)

def find_components(adj: dict) -> list[list]:
    visited: set = set()
    components: list[list] = []
    for v in adj:               # перебираем все вершины графа
        if v not in visited:
            component: list = []
            dfs_collect(adj, v, visited, component)
            components.append(component)
    return components

Проследим трассу на графе с вершинами {0,1,2,3,4} и рёбрами (0,1), (1,2), (3,4):

adj = {0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3]}

Первый запуск — из вершины 0 (не в visited):

• вход в 0: стек [0], visited {0}, component [0]
• вход в 1: стек [0, 1], visited {0, 1}, component [0, 1]
• из 1: сосед 0 уже в visited; вход в 2: стек [0, 1, 2], visited {0,1,2}, component [0,1,2]
• из 2: сосед 1 уже в visited; возврат → возврат → возврат
• компонента [0, 1, 2] добавлена

Внешний цикл продолжает: 1 в visited — пропуск; 2 в visited — пропуск.

Второй запуск — из вершины 3 (не в visited):

• вход в 3: стек [3], visited {0,1,2,3}, component [3]
• вход в 4: стек [3, 4], visited {0,1,2,3,4}, component [3,4]
• из 4: сосед 3 уже в visited; возврат → возврат
• компонента [3, 4] добавлена

Итог: [[0, 1, 2], [3, 4]]. Каждая вершина вошла ровно в одну компоненту — потому что visited общее и вершина, однажды посещённая, больше никогда не станет точкой запуска.

---

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

def reachable(adj: dict, source) -> set:
    visited: set = set()
    dfs(adj, source, visited)   # тот же рекурсивный DFS
    return visited

Пример:

adj_d = {0: [1, 2], 1: [3], 2: [], 3: [], 4: [0]}
print(reachable(adj_d, 0) == {0, 1, 2, 3})        # True
print(reachable(adj_d, 4) == {0, 1, 2, 3, 4})     # True
print(reachable(adj_d, 2) == {2})                  # True

Из вершины 2 нет исходящих рёбер — достижима только она сама. Из 4 есть ребро 4→0, поэтому достижима вся часть, достижимая из 0.

visited после этого запуска содержит достижимые вершины, но не те, из которых можно добраться до source. Ребро 4→0 означает, что 4 «видит» 0, но 0 не «видит» 4 — и 4 в reachable(adj_d, 0) не войдёт.

Чтобы найти вершины, из которых достижима source, можно обойти транспонированный граф, где направления всех рёбер обращены.