Топологічне сортування: Упорядкування DAG

Ordering a graph that has "before" and "after"

A directed acyclic graph (DAG) is exactly what it sounds like: edges have a direction, and there are no cycles — no way to follow directed edges and end up back where you started. Whenever the edges of a graph mean "must happen before" — compile this file before that one, finish this course before that one, calculate this spreadsheet cell before that one — a topological order is a full ordering of every node such that every edge points from an earlier node to a later one. It is the formal answer to "in what order can I safely do all of this."

Алгоритм Кайна: видаляйте вузли без залежностей

Найбільш інтуїтивно зрозумілий алгоритм (Кайн, 1962) відстежує степінь входу кожного вузла — кількість ребер, що вказують на нього, тобто кількість незавершених передумов, які має він. Будь-який вузол з ступенем входу рівним нулю не має блокуючих його вузлів, тому його можна вивести наступний; видалення його з графу знижує ступінь входу всіх вузлів, на які він вказував, можливо, звільняючи більше вузлів.

kahn(графа): indegree[v] = кількість входячих ребер для кожного вузла v queue = всі вузли з indegree == 0 order = []

while queue не порожня: u = queue.pop() order.append(u) for кожне ребро u -> v: indegree[v] -= 1 if indegree[v] == 0: queue.push(v)

if len(order) < загальна кількість вузлів: return "Виявлено цикл — не існує топологічного порядку" return order

live demo · видалення вузлів з нульовим ступенем входу з графа залежностей● LIVE

Кожен вузол та кожне ребро відвідуються постійну кількість разів, тому алгоритм Кайна працює за часом O(V + E). Порядок, який він генерує, не обов'язково є унікальним — будь-які два вузли, які ніколи не залежать один від одного, безпосередньо чи транзитивно, можуть з’явитися в будь-якому відносному порядку, тому DAG зазвичай допускає багато дійсних топологічних порядків.

kahn(graph):
  indegree[v] = number of incoming edges, for every node v
  queue = all nodes with indegree == 0
  order = []

  while queue not empty:
    u = queue.pop()
    order.append(u)
    for each edge u -> v:
      indegree[v] -= 1
      if indegree[v] == 0:
        queue.push(v)

  if len(order) < total node count:
    return "cycle detected — no topological order exists"
  return order

The DFS alternative: reverse postorder

A second, equally common approach runs a depth-first search from every unvisited node and records each node the moment its DFS call finishes — after all of its descendants have already finished. Reversing that finish-order list gives a valid topological order, because a node cannot finish before any node it points to has already finished (that descendant was necessarily visited, and finished, during the same DFS call). This version is elegant and needs no explicit indegree bookkeeping, but detecting a cycle requires tracking the current recursion stack separately (a "grey" node revisited while still on the stack signals a cycle), whereas Kahn’s algorithm gets cycle detection for free as a byproduct of the final count check.

Why cycles break everything

If the graph contains a cycle, no topological order can exist at all: every node in the cycle would need to come both before and after some other node in the same cycle, which is a logical contradiction. This is exactly why the leftover-nodes check in Kahn's algorithm works as cycle detection — nodes trapped inside a cycle always retain at least one incoming edge from within that same cycle and so never reach indegree zero, never get queued, and never make it into the output order.

Оптимізація рішень за допомогою динамічного програмування

Будівельні системи (Make, Bazel, task graphs npm/yarn) топологічно сортують граф залежностей цілей так, щоб кожна ціль будувалася лише після завершення всіх залежних від неї. Менеджери пакетів вирішують порядок встановлення аналогічним чином. Оцінка формул в курсових предметах (перерахування клітинки B2 лише після того, як усі посилані на неї клітинки стабілізуються), а також планувачі завдань у розподілених двигунах робочого процесу всі структурно зводяться до однієї проблеми: будуйте DAG «повинно відбутися раніше» відносин, потім запускайте алгоритм Kahn або DFS після обходу, щоб знайти безпечний порядок виконання — або виявити, що з залишків вузлів не існує безпечного порядку через введену циклічну залежність.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Topological Sort і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.