Временная сложность
O(V + E)
Топологическая сортировка создаёт линейный порядок вершин в ориентированном ациклическом графе (DAG), при котором для каждого направленного ребра u → v вершина u располагается раньше вершины v.
Как работает алгоритм Кана (на основе BFS):
1. Вычислить полустепень захода каждой вершины
2. Добавить в очередь все вершины с полустепенью захода 0
3. Пока очередь не пуста:
a. Извлечь вершину из очереди и добавить её в результат
b. Для каждого исходящего ребра уменьшить полустепень захода соседней вершины
c. Если полустепень захода соседней вершины стала равна 0, добавить её в очередь
4. Если обработаны все вершины, результат является корректным топологическим порядком
Временная сложность: O(V + E)
Пространственная сложность: O(V)
Применение:
- Планирование задач с зависимостями
- Системы сборки проектов (Make, Gradle)
- Планирование учебных курсов с учётом предварительных требований
- Разрешение зависимостей пакетов
Топологическая сортировка возможна только для DAG (ориентированных ациклических графов). Если граф содержит цикл, корректный порядок не существует.
Похожие алгоритмы
Частые вопросы
- Что такое Топологическая сортировка (алгоритм Кана)?
- Топологическая сортировка создаёт линейный порядок вершин в ориентированном ациклическом графе (DAG), при котором для каждого направленного ребра u → v вершина u располагается раньше вершины v.
- Какова сложность Топологическая сортировка (алгоритм Кана)?
- Время (среднее): O(V + E) · Память: O(V)
- Для кого предназначена визуализация Топологическая сортировка (алгоритм Кана)?
- Визуализация Топологическая сортировка (алгоритм Кана) рассчитана на продвинутый уровень в категории «Графы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Топологическая сортировка (алгоритм Кана)?
- В той же категории (Графы) вы можете изучить: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Каждый из них имеет интерактивную визуализацию.