Топологическая сортировка алгоритмом Кана
Упорядочивайте задачи, зависящие друг от друга
«Топологическая сортировка алгоритмом Кана» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое топологический порядок
Топологический порядок перечисляет все вершины ориентированного графа так, чтобы каждое ребро вело от более ранней вершины к более поздней. Сначала идут задачи, от которых зависят другие задачи.
Допустимы только DAG
Это работает только для DAG — ориентированного ацикличного графа. Если существует цикл, никакой допустимый порядок не сможет удовлетворить всем зависимостям.
Идея входящей степени
Алгоритм Кана опирается на входящую степень: количество рёбер, входящих в вершину. У вершины с нулевой входящей степенью нет невыполненных зависимостей.
Подсчитайте все входящие степени
Сначала пройдите по всем рёбрам и посчитайте, сколько раз каждая вершина оказывается пунктом назначения. Так вы получите входящую степень каждой вершины.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Заполните очередь готовых вершин
Любая вершина с нулевой входящей степенью уже готова, поэтому сначала поместите все такие вершины в очередь.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Обработайте одну вершину
Извлеките готовую вершину с помощью pop и append её в ваш порядок. Теперь это безопасно, потому что от неё больше ничего не зависит.
u = q.popleft()
order.append(u)Освободите соседей
Для каждого соседа уменьшите его входящую степень на единицу. Когда она достигает нуля, сосед становится готовым и добавляется в очередь.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Повторяйте, пока очередь не опустеет
Продолжайте извлекать вершины и освобождать их соседей, пока очередь не опустеет. Порядок растёт по одной безопасной вершине, пока в него не будут добавлены все вершины.
Обнаруживайте цикл без дополнительных затрат
Если итоговый порядок содержит меньше n вершин, оставшиеся оказались в ловушке цикла. Алгоритм Кана обнаруживает цикл без дополнительных затрат.
if len(order) < n:
print('cycle exists')Время работы
Каждую вершину и каждое ребро посещают один раз, поэтому алгоритм Кана работает за O(V + E). Он подходит даже для графов с миллионами рёбер.
Много допустимых порядков
Когда несколько вершин готовы одновременно, следующей можно выбрать любую из них. Поэтому у DAG часто бывает много допустимых топологических порядков, а не только один.
Быстрая проверка
Вы завершили алгоритм Кана, но порядок содержит меньше n вершин. Что это означает?
Итоги: алгоритм Кана
Подсчитайте входящие степени, поместите вершины с нулевой степенью в очередь, извлеките вершину, уменьшите степени её соседей и повторяйте. Так выполняется простая топологическая сортировка за O(V+E). 🚀
Часто задаваемые вопросы
Урок «Топологическая сортировка алгоритмом Кана» бесплатный?
Да — полный текст урока «Топологическая сортировка алгоритмом Кана» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Топологическая сортировка алгоритмом Кана»?
Упорядочивайте задачи, зависящие друг от друга Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Топологическая сортировка алгоритмом Кана»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Топологическая сортировка алгоритмом Кана
- Поиск циклов в ориентированных графах
- Компоненты сильной связности
- Мосты и точки сочленения