Калькулятор топологической сортировки
Вычисляет топологическую сортировку ориентированного ациклического графа алгоритмом Кана или обходом в глубину. Находит циклы и показывает их путь, строит вид параллельных уровней выполнения и анимирует каждый шаг на интерактивном графе.
Ваш блокировщик рекламы мешает нам показывать объявления
MiniWebtool остается бесплатным благодаря рекламе. Если этот инструмент помог вам, поддержите нас: перейдите на тариф без рекламы и с большим числом ежедневных запусков или разрешите MiniWebtool.com и обновите страницу.
- Разрешите рекламу для MiniWebtool.com и обновите страницу
- Или перейдите на тариф без рекламы и с более высокими дневными лимитами
О Калькулятор топологической сортировки
Калькулятор топологической сортировки вычисляет линейный порядок вершин ориентированного ациклического графа (DAG), при котором каждое направленное ребро от u к v ставит u перед v. Введите свой граф в виде списка ребер или списка смежности, и инструмент вернет топологический порядок, используя алгоритм Кана или пост-порядок DFS, обнаружит циклы (с точным путем цикла), сгруппирует задачи в слои параллельного выполнения, подсчитает количество допустимых порядков и анимирует каждый шаг на интерактивном графе.
Что такое топологическая сортировка?
Для данного ориентированного графа G = (V, E) топологическая сортировка (или топологический порядок) — это линейное расположение v₁, v₂, …, vₙ его вершин, такое, что для каждого ориентированного ребра (u → v) u появляется перед v в этом расположении. Топологический порядок существует тогда и только тогда, когда в графе нет направленных циклов, то есть граф является DAG. Порядок редко бывает уникальным: граф может иметь много допустимых топологических сортировок, когда сразу несколько вершин имеют нулевую степень захода.
когда для каждого ребра (u → v) в E: позиция(u) < позиция(v)
Алгоритмы, используемые в этом калькуляторе
Алгоритм Кана (на основе BFS, 1962)
Алгоритм Кана — самая интуитивно понятная топологическая сортировка. На каждом шаге он выбирает вершину с нулевой степенью захода (без входящих ребер), добавляет ее в выходные данные и «удаляет» ее из графа, уменьшая степень захода каждого из ее последователей. Когда несколько вершин имеют нулевую степень захода, для разрешения неоднозначности может использоваться min-heap (дающая лексикографически наименьший порядок) или очередь FIFO (дающая порядок вставки). Алгоритм Кана работает за время O(|V| + |E|) и служит детектором циклов: если после опустошения очереди какая-либо вершина все еще имеет степень захода > 0, значит, в графе есть цикл.
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|).
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. Метки вершин могут состоять из букв, цифр, подчеркиваний, тире и точек.
C -> D
Рубашка -> Галстук -> Пиджак
Список смежности
Запишите вершину, двоеточие и ее прямых последователей (вершины, на которые она указывает). Вершине без последователей все равно нужна своя строка, например D:.
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, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.
Продвинутые математические операции:
- Калькулятор матрицы смежности Новый
- Антилогарифмический Калькулятор
- Калькулятор бета-функции
- Калькулятор биномиального коэффициента
- Калькулятор биномиального распределения Популярное
- Побитовый калькулятор Популярное
- Упроститель Булевой Алгебры Новый
- Калькулятор центральной предельной теоремы
- Калькулятор китайской теоремы об остатках
- Комбинированный калькулятор
- Калькулятор дополнительной функции ошибки
- Калькулятор комплексных чисел Популярное
- Калькулятор цепных дробей
- Калькулятор беспорядков (субфакториал)
- Калькулятор кратчайшего пути Дейкстры
- Калькулятор Энтропии
- Калькулятор функции ошибки
- Калькулятор функции Эйлера
- Калькулятор экспоненциального распада
- Калькулятор экспоненциального роста: высокая точность
- Калькулятор экспоненциального интеграла
- Калькулятор показателей (высокая точность)
- Калькулятор расширенного алгоритма Евклида
- Калькулятор факториала
- Калькулятор гамма-функции
- Калькулятор золотого сечения
- Калькулятор раскраски графов Новый
- Валидатор последовательности степеней графа
- Калькулятор Порядка в Теории Групп Новый
- Калькулятор полураспада
- Проверка Гамильтонова Пути Новый
- Калькулятор формулы включений-исключений Новый
- Решатель Карты Карно (K-Map) Популярное
- Решатель Линейного Программирования Новый
- Калькулятор стационарного распределения цепи Маркова
- Калькулятор минимального остовного дерева
- Калькулятор Модульного Возведения в Степень Новый
- Калькулятор модулярного мультипликативного обратного
- Калькулятор отрицательного биномиального распределения Новый
- Калькулятор сетевого потока (Максимальный поток) Новый
- Калькулятор процентного роста
- Калькулятор перестановок
- Калькулятор перестановок с повторениями Новый
- Калькулятор принципа голубятни
- Проверка планарного графа Новый
- Калькулятор распределения Пуассона
- Калькулятор корней многочленов с подробными шагами
- Калькулятор первообразного корня
- Калькулятор вероятности
- Калькулятор распределения вероятностей
- Калькулятор пропорций Популярное
- Калькулятор квадратичных формул
- Калькулятор Колец и Полей Новый
- Калькулятор округления Новый
- Научный Калькулятор
- Калькулятор экспоненциальной записи
- Калькулятор теории множеств Популярное
- Калькулятор значащих цифр Новый
- Решатель задачи о стабильных браках Новый
- Калькулятор чисел Стирлинга
- Калькулятор суммы кубов
- Калькулятор суммы последовательных чисел
- Калькулятор суммы квадратов Популярное
- Калькулятор топологической сортировки Новый
- Решатель задачи коммивояжёра (TSP) Новый
- Генератор таблицы истинности
- Генератор диаграммы Венна (3 множества)