Що таке топологічне сортування в графах?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Топологічне сортування - це лінійний порядок вершин орієнтованого ациклічного графа (DAG), у якому для кожного ребра u→v вершина u йде раніше за вершину v. Воно існує лише для графів без циклів і зазвичай будується за O(V+E) за допомогою алгоритму Кана (через вхідні степені) або обходу в глибину (DFS).

Детальний розбір

Визначення

Топологічне сортування задає лінійне впорядкування всіх вершин орієнтованого ациклічного графа так, щоб кожне обмеження-залежність (ребро u→v) дотримувалося: u стоїть перед v. Порядок може бути не єдиним - за наявності «незалежних» вершин допустимі різні коректні послідовності.

Коли застосовна

Лише для орієнтованих ациклічних графів (DAG). Якщо є цикл - коректного порядку не існує.
Для виявлення циклу: в алгоритмі Кана - якщо після обробки залишилися вершини з ненульовою вхідною степінню; у DFS - виявлення зворотного ребра (вершини на стеку/сірого кольору).

Ключові властивості

Коректність: для кожного ребра u→v вершина u розташована раніше за v.
Існування: можливе лише для DAG; наявність циклу робить сортування неможливим.
Неєдиність: може бути багато валідних порядків. Єдиність досягається, якщо на кожному кроці алгоритму Кана вибір вершини однозначний (у черзі завжди рівно 1 вершина з нульовою вхідною степінню). Еквівалентно: у графі фактично задано «майже повний» порядок залежностей (є гамільтонів шлях).
Складність: обидва класичні алгоритми працюють за O(V+E) за часом і O(V+E) за пам'яттю.

Алгоритми

Алгоритм Кана (через вхідні степені):

Порахувати вхідну степінь кожної вершини.
Покласти в чергу всі вершини з нульовою вхідною степінню.
Поки черга не порожня: видалити вершину, додати у відповідь, «видалити» її ребра, зменшуючи вхідну степінь сусідів; ті, що з'явилися з нульовою степінню, - у чергу.
Якщо оброблено менше вершин, ніж є в графі - є цикл.

DFS-підхід (зворотний постпорядок):

Запустити DFS; перед виходом з вершини додавати її до списку.
Після обходу всіх компонентів графа розвернути список - це і є топологічний порядок.
Виявлення циклу: потрапляння в «сіру» вершину (на стеку рекурсії) означає цикл.

Приклад графа і коректних порядків

Нехай вершини: 0,1,2,3,4. Ребра: 0→2, 1→2, 1→3, 3→4. Коректні топологічні порядки включають, наприклад: [1,0,3,4,2], [0,1,3,4,2], [1,3,4,0,2]. Зауважте, що 0 і 1 незалежні одна від одної і можуть йти в будь-якому порядку до 2.

Код: алгоритм Кана (JavaScript)

/*
  n - кількість вершин (0..n-1)
  edges - масив пар [u, v] для ребер u→v
  Повертає { order, unique } або кидає помилку за наявності циклу
*/
function topoSortKahn(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = Array(n).fill(0);
  for (const [u, v] of edges) {
    adj[u].push(v);
    indeg[v]++;
  }

  const queue = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);

  const order = [];
  let unique = true; // буде хибним, якщо на якомусь кроці є вибір із >1 вершини

  while (queue.length) {
    if (queue.length > 1) unique = false;
    // Можна відсортувати queue для детермінізму, але це змінює лише вигляд порядку, не коректність
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) {
      indeg[v]--;
      if (indeg[v] === 0) queue.push(v);
    }
  }

  if (order.length !== n) {
    throw new Error("Граф містить цикл: топологічне сортування неможливе");
  }

  return { order, unique };
}

// Приклад використання:
const n = 5;
const edges = [ [0,2], [1,2], [1,3], [3,4] ];
const result = topoSortKahn(n, edges);
console.log(result.order);  // Наприклад: [1,0,3,4,2]
console.log(result.unique); // false - на кроках був вибір

Код: реалізація DFS (Python)

from typing import List, Tuple

# n - кількість вершин (0..n-1)
# edges - список ребер (u, v) для u→v
# Повертає список вершин у топологічному порядку

def topo_sort_dfs(n: int, edges: List[Tuple[int, int]]) -> List[int]:
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []

    def dfs(u: int):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                raise ValueError("Граф містить цикл: топологічне сортування неможливе")
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        order.append(u)  # зворотний постпорядок

    for u in range(n):
        if color[u] == WHITE:
            dfs(u)

    order.reverse()
    return order

# Приклад використання
n = 5
edges = [(0, 2), (1, 2), (1, 3), (3, 4)]
print(topo_sort_dfs(n, edges))  # Наприклад: [1, 0, 3, 4, 2]

Перевірка унікальності порядку

Під час алгоритму Кана стежте за розміром черги: якщо коли-небудь у ній більше однієї вершини з нульовою вхідною степінню, єдиності немає. Якщо на кожному кроці рівно одна вершина - порядок єдиний.

Застосування

Планування завдань із залежностями (CI/CD пайплайни, оркестрація кроків).
Збирання проєктів і системи модулів (визначення порядку компіляції/лінкування).
Розв'язання залежностей пакетів, завантаження модулів/міграцій БД у правильному порядку.
Курси з передумовами; обчислення порядку проходження.

Часті помилки

Застосування до графа з циклами - потрібно або видаляти цикл, або сигналізувати про помилку.
У DFS додають вершину до обходу дітей - правильно додавати після обходу (постпорядок) і потім розвертати.
Забувають обробляти ізольовані вершини (без ребер) - вони повинні бути присутні в порядку.
Неправильна інтерпретація напрямку ребра (міняють місцями залежність і залежний вузол).
Очікування єдиного результату там, де граф допускає кілька коректних порядків.

Складність

І алгоритм Кана, і DFS-варіант працюють за O(V+E) за часом; за пам'яттю зберігають граф і додаткові структури (вхідні степені/кольори, чергу/стек), що також укладається в O(V+E).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.