Вопрос 1 — Алгоритм топологической сортировки

Теоретический билет. Ниже: определение → существование → два алгоритма (DFS и Кан) с иллюстрациями → корректность → асимптотика → что говорить на устном.

ОпределениеСуществованиеDFS-алгоритмАлгоритм КанаКак отвечать

1. Определение

Топологическая сортировка. Рассмотрим ориентированный граф; присвоим каждой вершине номер. Перестановка σ называется топологической сортировкой, если для любого ребра (u, v) ∈ E выполнено σ(u) < σ(v).

Простыми словами: выстроить вершины в линию так, чтобы все рёбра шли только слева направо — из вершины с меньшим номером в вершину с большим.
0 1 2 3 поз. 1 поз. 2 поз. 3 поз. 4

Рёбра: 0→1, 0→2, 1→2, 1→3, 2→3

Топологический порядок: 0, 1, 2, 3

Каждая стрелка идёт слева направо. Это и значит σ(u)<σ(v) для всех рёбер.

Порядок не единственный: например 0, 1, 2, 3 — единственный здесь, но в разреженных графах вариантов бывает много.

2. Когда существует

Утверждение. Топологическая сортировка существует тогда и только тогда, когда граф ацикличен (является DAG — directed acyclic graph).

В одну сторону (есть цикл → сортировки нет). Порядок «меньше» сам по себе ацикличен: нельзя иметь σ(a)<σ(b)<…<σ(a). Если в графе есть цикл a→b→…→a, то по рёбрам цикла требовалось бы σ(a)<σ(b)<…<σ(a) — противоречие. Значит при наличии цикла сортировки не существует.

В обратную сторону (нет цикла → сортировка есть). Доказывается конструктивно — приведением алгоритма, который её строит (см. ниже). Раз алгоритм всегда находит порядок на любом DAG, значит он существует.

a b c

Цикл a→b→c→a: куда ни поставь a, найдётся ребро, идущее «назад». Топопорядка нет.

3. Алгоритм через DFS (как в лекции)

Шаги

  1. Запустить DFS на всём графе (перебирая все вершины как стартовые).
  2. В момент выхода из вершины (когда красим её в чёрный) добавлять её в конец массива.
  3. В конце развернуть массив — он содержит топологическую сортировку.
Главная идея одной фразой: топосорт = вершины, отсортированные по убыванию времени выхода t_out.

Почему это работает (корректность)

Ключевое наблюдение: при обходе в глубину время выхода t_out[v] всегда больше, чем t_out любой вершины, достижимой из v. Почему — потому что все достижимые из v вершины посещаются либо до вызова DFS(v), либо во время него (внутри его рекурсии), и из них выходят раньше, чем из самого v.

Значит для любого ребра (u, v): из u выходим позже, чем из v, то есть t_out[u] > t_out[v]. Если отсортировать по убыванию t_out — u окажется раньше v. Это ровно условие σ(u)<σ(v). А так как мы добавляем вершины в порядке возрастания t_out, достаточно развернуть массив.

Прогон на примере 0→1, 0→2, 1→2, 1→3, 2→3

Запускаем DFS из 0. Условно идём по соседям в порядке возрастания номера.

событиеt_outмассив (по выходу)
выход из 31[3]
выход из 22[3, 2]
выход из 13[3, 2, 1]
выход из 04[3, 2, 1, 0]
Разворот → [0, 1, 2, 3] — топологический порядок. ✓

Код (DFS-версия)

import sys
def topo_sort_dfs(n, adj):
    color = [0] * n           # 0 белый, 1 серый, 2 чёрный
    order = []
    has_cycle = [False]

    def dfs(v):
        color[v] = 1
        for u in adj[v]:
            if color[u] == 0:
                dfs(u)
            elif color[u] == 1:   # ребро в серую = цикл
                has_cycle[0] = True
        color[v] = 2
        order.append(v)            # добавляем при ВЫХОДЕ

    for v in range(n):
        if color[v] == 0:
            dfs(v)

    return order[::-1] if not has_cycle[0] else None

На Python длинные цепочки могут переполнить стек рекурсии — поднять лимит sys.setrecursionlimit(...) или писать итеративно.

4. Алгоритм Кана (альтернатива через входящие степени)

Интуиция: indeg[v] — число невыполненных предусловий вершины. Берём то, что доступно сейчас (indeg=0), «выполняем», освобождаем зависящих. Полностью итеративный, без рекурсии.

Шаги

  1. Посчитать indeg[v] — число входящих рёбер (один проход по рёбрам).
  2. В очередь положить все вершины с indeg = 0.
  3. Пока очередь не пуста: достать v, добавить в порядок; у всех соседей indeg -= 1; кто стал 0 — в очередь.
  4. Если в порядок попали все N вершин — это топосорт. Если меньше — есть цикл.

Почему даёт топопорядок

Вершину берём, только когда её indeg стал 0, то есть все её предшественники уже обработаны раньше. Значит по каждому ребру u→v вершина u вышла раньше v — ровно условие топосорта.

Почему детектирует цикл

У вершин цикла indeg никогда не обнулится: они держат друг другу по входящему ребру внутри цикла. Они не попадут в очередь → обработано меньше N вершин ⇔ цикл.

Прогон на том же графе

шагочередьберёмindeg послепорядок
старт[0]—1:1 2:2 3:2[]
1[1]01:0 2:1 3:2[0]
2[2]12:0 3:1[0,1]
3[3]23:0[0,1,2]
4[]3—[0,1,2,3]
Порядок [0, 1, 2, 3], обработали 4 = N → цикла нет. ✓

Код (Кан)

from collections import deque
def topo_sort_kahn(n, adj):
    indeg = [0] * n
    for v in range(n):
        for u in adj[v]:
            indeg[u] += 1
    dq = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while dq:
        v = dq.popleft()
        order.append(v)
        for u in adj[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                dq.append(u)
    return order if len(order) == n else None   # None = есть цикл

5. Сравнение двух подходов

DFS-версияКан (indeg)
Идеясортировка по убыванию t_outснимаем вершины с indeg=0
Время / ПамятьO(V+E) / O(V)O(V+E) / O(V+E)
Рекурсияда (риск переполнения стека)нет, итеративно
Детекция цикларебро в серую вершинуобработано < N
Лекс. мин. порядокнеудобнолегко: min-куча вместо deque

6. Как отвечать на устном (скелет)

  1. Определение: перестановка σ, что для всех рёбер (u,v) выполнено σ(u)<σ(v) — рёбра только «вперёд».
  2. Существование: ⇔ граф ацикличен (DAG). При цикле σ(a)<…<σ(a) — противоречие.
  3. Алгоритм (DFS): DFS на всём графе, добавляем вершину при выходе, разворачиваем. Это сортировка по убыванию t_out.
  4. Корректность: t_out[u] > t_out[всех достижимых из u], значит по ребру (u,v) → t_out[u]>t_out[v] → после разворота u раньше v.
  5. Асимптотика: O(V+E).
  6. Бонус: упомянуть алгоритм Кана (через indeg) и детекцию цикла.
Уточняющие вопросы, к которым готовься: