Калькулятор топологической сортировки

Вычислите топологический порядок ориентированного ациклического графа (DAG), используя алгоритм Кана или поиск в глубину (DFS). Инструмент обнаруживает циклы, сообщает путь цикла, строит послойное представление для параллельного выполнения, поддерживает лексикографически минимальный порядок и анимирует каждый шаг на интерактивном графе.

⚡ Попробуйте пример:

Линейная цепь Порядок одевания Курсы обучения Утренний распорядок Цели сборки Образец смежности С циклом Pipeline DAG

Формат ввода

→ Список ребер

⧇ Список смежности

Данные графа

Формат ребра: A -> B (также принимаются →, =>, :). Макс. 80 вершин / 800 ребер.

Формат смежности: A: B, C, D — одна вершина на строку, за которой следуют ее прямые последователи.

Алгоритм

Алгоритм Кана (лексикографический) дает уникальный, воспроизводимый порядок. Пост-порядок DFS — это классический метод поиска в глубину.

Embed Калькулятор топологической сортировки Widget

О Калькулятор топологической сортировки

Калькулятор топологической сортировки вычисляет линейный порядок вершин ориентированного ациклического графа (DAG), при котором каждое направленное ребро от u к v ставит u перед v. Введите свой граф в виде списка ребер или списка смежности, и инструмент вернет топологический порядок, используя алгоритм Кана или пост-порядок DFS, обнаружит циклы (с точным путем цикла), сгруппирует задачи в слои параллельного выполнения, подсчитает количество допустимых порядков и анимирует каждый шаг на интерактивном графе.

Что такое топологическая сортировка?

Для данного ориентированного графа G = (V, E) топологическая сортировка (или топологический порядок) — это линейное расположение v₁, v₂, …, vₙ его вершин, такое, что для каждого ориентированного ребра (u → v) u появляется перед v в этом расположении. Топологический порядок существует тогда и только тогда, когда в графе нет направленных циклов, то есть граф является DAG. Порядок редко бывает уникальным: граф может иметь много допустимых топологических сортировок, когда сразу несколько вершин имеют нулевую степень захода.

Определение топологического порядка

Перестановка (v₁, v₂, …, v_n) множества V является топологической тогда и только тогда,
когда для каждого ребра (u → v) в E: позиция(u) < позиция(v)

Алгоритмы, используемые в этом калькуляторе

Алгоритм Кана (на основе BFS, 1962)

Алгоритм Кана — самая интуитивно понятная топологическая сортировка. На каждом шаге он выбирает вершину с нулевой степенью захода (без входящих ребер), добавляет ее в выходные данные и «удаляет» ее из графа, уменьшая степень захода каждого из ее последователей. Когда несколько вершин имеют нулевую степень захода, для разрешения неоднозначности может использоваться min-heap (дающая лексикографически наименьший порядок) или очередь FIFO (дающая порядок вставки). Алгоритм Кана работает за время O(|V| + |E|) и служит детектором циклов: если после опустошения очереди какая-либо вершина все еще имеет степень захода > 0, значит, в графе есть цикл.

Алгоритм Кана (псевдокод)

Kahn(G):
  Q ← { v ∈ V : indeg(v) = 0 }
  L ← [ ]
  while Q не пуста:
    u ← Q.pop()
    L.append(u)
    for каждое ребро u → v:
      indeg(v) -= 1
      if indeg(v) = 0: Q.push(v)
  if |L| < |V|: сообщить о цикле
  else: вернуть L

Пост-порядок DFS (Тарьян, 1976)

Алгоритм DFS выполняет поиск в глубину, и когда вершина завершается (то есть все ее последователи были полностью исследованы), она помещается в стек. Реверсирование стека в конце дает допустимый топологический порядок. Обнаружение циклов происходит естественно: встреча с вершиной, которая все еще находится в процессе исследования (помечена СЕРЫМ), означает, что найдено обратное ребро, следовательно, граф не является DAG. Пост-порядок DFS также работает за время O(|V| + |E|).

Пост-порядок DFS (псевдокод)

DFS-Topo(G):
  for каждую вершину u в V: color[u] ← WHITE
  L ← пустой стек
  for каждую вершину u в V:
    if color[u] = WHITE: visit(u)
  return reverse(L)

visit(u):
  color[u] ← GRAY
  for каждое ребро u → v:
    if color[v] = GRAY: сообщить о цикле
    if color[v] = WHITE: visit(v)
  color[u] ← BLACK; L.push(u)

Слои параллельного выполнения

Послойное представление DAG разделяет его вершины на уровни так, что каждое ребро идет с уровня с меньшим номером на уровень с большим. Вершины в одном слое независимы друг от друга, поэтому они могут выполняться параллельно. Количество слоев равно длине самого длинного пути плюс один — это критический путь DAG, минимальное количество последовательных раундов, необходимых для завершения всех задач даже при неограниченном параллелизме. Этот калькулятор автоматически создает послойный вид, если входные данные являются DAG.

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

Если граф содержит ориентированный цикл, топологическая сортировка невозможна. Наш калькулятор сообщает точный путь цикла (например, A → B → C → A) и выделяет ребра цикла красным цветом на визуализации. Удаления любого одного ребра в цикле достаточно для восстановления ацикличности.

Форматы ввода

Список ребер

Записывайте каждое направленное ребро как источник -> цель, разделяя их запятыми или новыми строками. Допустимые варианты стрелок: ->, →, =>, -->, :. Вы также можете объединять ребра в цепочки: A -> B -> C — это сокращение для A->B и B->C. Метки вершин могут состоять из букв, цифр, подчеркиваний, тире и точек.

A -> B, B -> C, A -> C
C -> D
Рубашка -> Галстук -> Пиджак

Список смежности

Запишите вершину, двоеточие и ее прямых последователей (вершины, на которые она указывает). Вершине без последователей все равно нужна своя строка, например D:.

A: B, C
B: D
C: D
D:

Как пользоваться этим калькулятором

Выберите формат: Переключайтесь между списком ребер и списком смежности с помощью переключателей.
Введите граф: Вставьте свои данные или нажмите на один из быстрых примеров (порядок одевания, учебные курсы, цели сборки, граф с циклом и другие).
Выберите алгоритм: Лексикографический Кана для уникального, воспроизводимого порядка; порядок вставки для сохранения очередности ввода; пост-порядок DFS для классического метода поиска в глубину; или «Показать все», чтобы увидеть все варианты рядом.
Нажмите «Сортировать топологически»: Ниже появятся порядок, данные об обнаружении цикла, послойный вид, длина критического пути, общее количество допустимых порядков и интерактивный граф.
Исследуйте: Нажмите «Играть», чтобы увидеть выдачу каждой вершины шаг за шагом. Значки входящих степеней обновляются в реальном времени. Перетаскивайте любой узел для изменения компоновки.

Реальное применение

Системы сборки и компиляторы

Такие инструменты, как make, Bazel, Gradle и npm, выполняют топологическую сортировку целей сборки, чтобы каждая цель компилировалась только после всех своих зависимостей. Цикл в графе зависимостей обычно выдается как фатальная ошибка — система сборки не может решить, с чего начать.

Планирование задач

Менеджеры проектов используют DAG для фиксации зависимостей задач. Топологическая сортировка дает допустимый порядок выполнения, а послойный вид — минимальное количество раундов при неограниченном параллелизме. Самая длинная цепь — это критический путь, определяющий общую продолжительность проекта.

Планирование учебных курсов

Каталог университетских курсов — это DAG: ребра являются отношениями предварительных условий. Топологический порядок — это допустимый план обучения, а слои подсказывают студентам, какие наборы курсов они могут изучать параллельно в каждом семестре.

Пересчет электронных таблиц

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

Менеджеры пакетов и загрузчики плагинов

Apt, pip, Homebrew, Maven и бесчисленные фреймворки плагинов определяют порядок установки или загрузки путем топологической сортировки своих DAG зависимостей.

Разрешение символов и планирование инструкций

Компиляторы используют топологическую сортировку для упорядочивания объявлений, а процессоры используют DAG зависимостей данных для планирования инструкций в буфере переупорядочивания без нарушения зависимостей по данным.

Подсчет топологических порядков

Для DAG с n вершинами количество различных допустимых топологических порядков может варьироваться от 1 (для полностью упорядоченной цепи) до n! (для графа без ребер). Вычисление точного количества в общем случае является #P-полной задачей, но для графов до 16 вершин этот калькулятор перечисляет их, используя формулу динамического программирования по маскам: f(S) = Σ f(S ∪ {v}) по всем v ∉ S, чьи предшественники уже находятся в S.

Сложность и производительность

Время: Как алгоритм Кана, так и пост-порядок DFS работают за O(|V| + |E|) — линейно от размера графа.
Память: O(|V|) для отслеживания входящих степеней и выходного порядка, плюс O(|V| + |E|) для структуры смежности.
Обнаружение циклов: Встроено в оба алгоритма. Алгоритм Кана обнаруживает циклы, когда |выход| < |V|; DFS обнаруживает их, когда найдено обратное ребро (СЕРЫЙ сосед).
Ограничения инструмента: до 80 вершин и 800 ребер для интерактивной визуализации. Подсчет порядков ограничен 16 вершинами.

Часто задаваемые вопросы

Что такое топологическая сортировка?

Топологическая сортировка ориентированного ациклического графа — это линейное упорядочение его вершин, при котором каждое направленное ребро от u к v ставит u перед v. Она представляет собой допустимый порядок обработки задач с соблюдением их зависимостей.

Какой алгоритм использует этот калькулятор?

Калькулятор запускает как алгоритм Кана, так и пост-порядок DFS. Алгоритм Кана многократно удаляет вершину с нулевой степенью захода и уменьшает степени захода ее последователей. Пост-порядок DFS выполняет поиск в глубину и инвертирует порядок завершения. Оба работают за время O(|V| + |E|).

Что если в моем графе есть цикл?

Граф с ориентированным циклом не имеет топологической сортировки. Калькулятор обнаруживает цикл, выделяет его красным цветом на визуализации и сообщает точный путь цикла, чтобы вы могли видеть, какие ребра нужно удалить, чтобы сделать граф DAG.

Что такое лексикографически наименьший топологический порядок?

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

Что такое послойный вид или вид по уровням?

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

Может ли граф иметь несколько допустимых топологических порядков?

Да. Если на любом шаге алгоритма Кана имеется несколько вершин с нулевой степенью захода, любая из них может быть выбрана следующей. Этот калькулятор подсчитывает точное количество различных топологических порядков для графов до 16 вершин.

В чем разница между алгоритмом Кана и пост-порядком DFS?

Алгоритм Кана работает сверху вниз: он многократно выбирает источники (степень захода 0) и выдает их первыми. Пост-порядок DFS работает снизу вверх: он сначала завершает стоки и добавляет их в начало порядка. Оба имеют сложность O(|V| + |E|) и создают допустимые топологические порядки, но обычно разные. Алгоритм Кана легче параллелизуется и адаптируется для лексикографического упорядочивания; DFS легче комбинировать с другими видами анализа на основе DFS, такими как поиск сильно связных компонентов.

Каков максимальный размер графа, поддерживаемый этим инструментом?

Калькулятор поддерживает до 80 вершин и 800 ребер. Подсчет общего количества допустимых топологических порядков ограничен 16 вершинами, так как задача является #P-полной и пространство состояний растет как 2ⁿ. Интерактивная визуализация и анимация алгоритмов плавно масштабируются до полного размера.

Дополнительная литература

Ссылайтесь на этот контент, страницу или инструмент так:

"Калькулятор топологической сортировки" на сайте https://ru.miniWebtool.com/калькулятор-топологической-сортировки/ от MiniWebtool, https://MiniWebtool.com/

командой miniwebtool. Обновлено: 20 апреля 2026 г.

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.