Перейти к содержанию

lab06 — графы и топологическая сортировка

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

Хранилище списка смежности — обычный dict (в отличие от lab05, где хеш-таблица писалась руками): здесь предмет лабораторной — алгоритмы на графе, а не контейнер под него. Длины списков по-прежнему считаются собственной array_length из common.

Содержание

Что такое граф и список смежности

Граф — это вершины (vertices) и рёбра (edges) между ними. В ориентированном графе ребро имеет направление: A -> B не то же самое, что B -> A. Для зависимостей это принципиально: «app зависит от db» — направленное утверждение.

Хранить граф можно двумя способами:

Представление Что это Память Проверить ребро A→B Перебрать соседей A
Список смежности (adjacency list) для каждой вершины — список её соседей O(V + E) O(degree) O(degree)
Матрица смежности (adjacency matrix) таблица V×V из 0/1 O(V²) O(1) O(V)

Для разреженных графов (рёбер немного — а зависимости сервисов именно такие) список смежности экономнее: реальные графы обычно имеют V вершин и порядка V, а не V² рёбер. Поэтому в лабораторной — список смежности.

web    -> api
api    -> db, cache
worker -> db, queue
db, cache, queue -> (нет рёбер)

DirectedGraph — граф на списке смежности

Внутри — dict {вершина: [соседи...]}. Порядок вставки вершин и рёбер сохраняется (в Python dict упорядочен с 3.7), и это важно: благодаря ему обходы детерминированы, а топологический порядок воспроизводим.

class DirectedGraph:
    def __init__(self) -> None:
        self._adjacency: dict = {}        # {вершина: список исходящих соседей}

    def add_vertex(self, vertex) -> None:
        if vertex not in self._adjacency:
            self._adjacency[vertex] = []  # идемпотентно

    def add_edge(self, src, dst) -> None:
        self.add_vertex(src)              # концы создаются автоматически
        self.add_vertex(dst)
        neighbors = self._adjacency[src]
        for existing in neighbors:
            if existing == dst:
                return                    # параллельное ребро не дублируем
        neighbors.append(dst)
  • add_edge сам создаёт отсутствующие вершины — граф можно строить одними рёбрами.
  • Дублирующее ребро игнорируется: на корректность обходов это не влияет, но искажало бы степени вершин и засоряло бы вывод.
  • neighbors() возвращает копию списка соседей — снаружи внутреннюю структуру не испортить.

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

BFS (breadth-first search) идёт «волнами»: стартовая вершина, потом все её соседи, потом соседи соседей. Реализован на очереди (FIFO): берём из головы, кладём непосещённых соседей в хвост.

def bfs(graph, start) -> list:
    order, visited = [], set()
    queue = [start]
    visited.add(start)
    head = 0                              # «указатель головы» вместо pop(0)
    while head < array_length(queue):
        current = queue[head]
        head += 1
        order.append(current)
        for neighbor in graph.neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)     # помечаем при ПОСТАНОВКЕ в очередь
                queue.append(neighbor)
    return order

Два нюанса:

  • Вершина помечается посещённой при добавлении в очередь, а не при извлечении. Иначе один и тот же сосед мог бы попасть в очередь несколько раз (через разные пути) до того, как до него дойдёт обработка.
  • Вместо queue.pop(0) (это O(n) — сдвигает весь список) держим индекс головы head. Так каждое извлечение — O(1).

Для графа-ромба 1->2, 1->3, 2->4, 3->4 обход от 1 даёт [1, 2, 3, 4]: сначала уровень {1}, потом {2, 3}, потом {4}. BFS находит кратчайший путь (в рёбрах) от старта до каждой достижимой вершины.

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

DFS (depth-first search) уходит как можно глубже по первому непосещённому соседу и откатывается, только упёршись в тупик. Реализован на явном стеке (LIFO), а не рекурсией — чтобы не упереться в лимит рекурсии Python на больших графах.

def dfs(graph, start) -> list:
    order, visited = [], set()
    stack = [start]
    while array_length(stack) > 0:
        current = stack.pop()             # снимаем с вершины стека
        if current in visited:
            continue                      # уже обработана через другой путь
        visited.add(current)
        order.append(current)
        neighbors = graph.neighbors(current)
        i = array_length(neighbors) - 1   # кладём соседей в ОБРАТНОМ порядке,
        while i >= 0:                     # чтобы первый сосед оказался сверху
            if neighbors[i] not in visited:
                stack.append(neighbors[i])
            i -= 1
    return order

Нюансы:

  • Соседи кладутся в стек в обратном порядке — тогда первый сосед окажется на вершине стека и обработается первым, как в естественной рекурсии (слева направо).
  • На стеке вершина может оказаться несколько раз (через разные пути), поэтому проверка if current in visited: continue стоит при извлечении, а не при добавлении.

Для того же ромба DFS от 1 даёт [1, 2, 4, 3]: из 1 идём в 2, из 2 вглубь в 4 (тупик), откат к 3 (а 4 уже посещена). Сравните с BFS [1, 2, 3, 4] — обходят те же вершины, но в разном порядке.

BFS (в ширину) DFS (в глубину)
Структура очередь (FIFO) стек (LIFO) / рекурсия
Идёт по уровням вглубь до тупика
Находит кратчайший путь (в рёбрах) любой путь; основа топосорта и поиска цикла
Аналогия круги на воде блуждание по лабиринту с откатами

Обнаружение цикла

В ориентированном графе цикл ищем трёхцветным DFS (раскраска вершин):

  • белая — ещё не посещалась;
  • серая — сейчас в стеке обработки (мы «внутри» неё);
  • чёрная — она и всё её поддерево полностью разобраны.

Ключевая идея: если из текущей вершины есть ребро в серую вершину — это обратное ребро (back edge), и оно замыкает цикл. Ребро в чёрную вершину цикла не даёт (то поддерево уже закрыто, назад оно не ведёт).

_WHITE, _GRAY, _BLACK = 0, 1, 2

def has_cycle(graph) -> bool:
    color = {v: _WHITE for v in graph.vertices()}
    for root in graph.vertices():
        if color[root] != _WHITE:
            continue
        stack = [[root, 0]]               # пары (вершина, индекс следующего соседа)
        color[root] = _GRAY
        while array_length(stack) > 0:
            frame = stack[-1]
            vertex, idx = frame[0], frame[1]
            neighbors = graph.neighbors(vertex)
            if idx < array_length(neighbors):
                frame[1] = idx + 1
                neighbor = neighbors[idx]
                if color[neighbor] == _GRAY:
                    return True           # ребро в серую вершину — цикл
                if color[neighbor] == _WHITE:
                    color[neighbor] = _GRAY
                    stack.append([neighbor, 0])
            else:
                color[vertex] = _BLACK    # все соседи разобраны — закрываем
                stack.pop()
    return False
  • DFS запускается из каждой ещё белой вершины — граф может быть несвязным, и цикл может прятаться в любой компоненте.
  • На стеке вместе с вершиной хранится индекс следующего соседа — так итеративный DFS «помнит», где остановился, имитируя кадры рекурсии.
  • Петля A -> A — простейший цикл: при разборе A (она серая) встречаем ребро в серую A.

Топологическая сортировка (алгоритм Кана)

Топологическая сортировка упорядочивает вершины так, что для каждого ребра src -> dst вершина src стоит раньше dst. Существует только для DAG (directed acyclic graph — ориентированного графа без циклов): при цикле «раньше» определить нельзя (a раньше b, b раньше c, c раньше a — противоречие).

Алгоритм Кана работает через степени входа (in-degree — число входящих рёбер):

  1. Посчитать in-degree каждой вершины.
  2. В очередь — все вершины с in-degree == 0 (ни от кого не зависят).
  3. Снять вершину из очереди → в результат; у всех её соседей уменьшить in-degree; если у соседа стал 0 — в очередь.
  4. Если в результат попали не все вершины — остался цикл (его вершины так и не получили нулевую степень).
def topological_sort(graph) -> list:
    in_degree = {v: 0 for v in graph.vertices()}
    for v in graph.vertices():
        for neighbor in graph.neighbors(v):
            in_degree[neighbor] += 1

    queue = [v for v in graph.vertices() if in_degree[v] == 0]
    order, head = [], 0
    while head < array_length(queue):
        current = queue[head]; head += 1
        order.append(current)
        for neighbor in graph.neighbors(current):
            in_degree[neighbor] -= 1      # «убрали» вершину — ослабили зависимость
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if array_length(order) != array_length(graph.vertices()):
        raise CycleError("в графе есть цикл (циклическая зависимость)")
    return order

Цикл сигнализируется исключением CycleError — это честнее, чем вернуть частичный или пустой список: вызывающий код обязан обработать невозможность построить порядок.

От топосортировки к порядку запуска

В нашей модели ребро app -> db значит «app зависит от db». Топосортировка даёт «зависимый раньше зависимости» (app перед db), а запускать надо наоборот — сперва то, от чего зависят. Поэтому startup_order просто разворачивает результат:

def startup_order(graph) -> list:
    order = topological_sort(graph)       # app, web, ... перед db, cache
    return order[::-1]                    # разворот: сначала зависимости

Для графа сервисов это даёт корректный порядок: db, cache, queue поднимаются раньше api и worker, а api — раньше web.

Сложность — итог

V — число вершин, E — число рёбер.

Операция Сложность Память
add_vertex O(1) —
add_edge O(degree) — проверка дубля —
bfs / dfs O(V + E) O(V)
has_cycle O(V + E) O(V)
topological_sort / startup_order O(V + E) O(V)

Все обходы — линейные по размеру графа O(V + E): каждую вершину обрабатываем один раз и каждое ребро проходим один раз. Это и есть «нормальная» сложность для графовых алгоритмов; для разреженного графа (E ≈ V) — фактически O(V).

Где это в проде

Граф зависимостей и топологическая сортировка — это буквально то, как системы решают «что от чего зависит и в каком порядке запускать»:

  • Порядок запуска сервисов. systemd строит граф юнитов из After=/Requires=/Wants= и топологически вычисляет порядок старта (и обратный — для остановки). В docker-compose директива depends_on задаёт рёбра графа, по которому Compose поднимает контейнеры в нужном порядке. Это ровно startup_order из лабораторной.
  • Граф ресурсов Terraform. terraform строит DAG ресурсов: ссылка aws_instance.web на aws_security_group.sg — это ребро зависимости. По топологическому порядку Terraform создаёт ресурсы (а при destroy — в обратном). terraform graph выводит этот DAG. Цикл зависимостей — ошибка Cycle: ..., которую Terraform ловит ровно так же, как has_cycle.
  • DAG в Airflow / CI-пайплайнах. Apache Airflow — это Directed Acyclic Graph в самом названии: задачи (tasks) с зависимостями t1 >> t2, исполняемые в топологическом порядке. Те же DAG-зависимости — в стадиях GitLab CI / GitHub Actions (needs:), в системах сборки (make, Bazel): что собрать раньше, чтобы артефакт был готов к моменту использования.
  • Обнаружение циклических зависимостей. Циклы в зависимостях — это баг, который надо находить: циклический import в Python/Go, циклы между микросервисами (A ждёт B, B ждёт A — дедлок при старте), циклы в зависимостях пакетов (npm, go mod). Алгоритм has_cycle (трёхцветный DFS) — основа линтеров и инструментов вроде madge (JS), import-linter (Python), которые отказываются собирать систему с циклом.

Меню

menu создаёт пример-граф сервисов и в цикле читает выбор:

Пункт Действие
1 Показать граф (список смежности)
2 Добавить вершину
3 Добавить ребро (зависимость A → B)
4 BFS от вершины
5 DFS от вершины
6 Проверить граф на цикл
7 Топологическая сортировка
8 Порядок запуска сервисов (startup order)
9 Демонстрация на графе сервисов (обходы + порядок старта)
10 Демонстрация графа с циклом (a → b → c → a)
0 Выход

Пункт 9 (demo_services) показывает весь конвейер на ацикличном графе сервисов, пункт 10 (demo_cycle) — что происходит при циклической зависимости: has_cycle находит цикл, а topological_sort отказывается строить порядок и бросает CycleError.