0Pricing
DSA Interview Prep · Урок

Алгоритм Кана: топологическая сортировка с помощью BFS

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

«Алгоритм Кана: топологическая сортировка с помощью BFS» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

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

Топологическая сортировка ориентированного ацикличного графа (DAG) — это упорядочивание его узлов, при котором каждое ориентированное ребро u → v означает, что u стоит в порядке раньше v. Она задаёт допустимый порядок выполнения задач с зависимостями — например, при сборке проекта, составлении расписания курсов или управлении пакетами. Допустимый топологический порядок существует только у DAG; наличие цикла делает его невозможным.

Алгоритм Кана: основная идея

Алгоритм Кана — это подход к топологической сортировке на основе BFS. Ключевая идея: узел с входящей степенью 0 (без предварительных условий) можно поставить первым в порядок. После этого удалите его и уменьшите входящую степень его соседей. Новые узлы с нулевой входящей степенью становятся доступными. Повторяйте процесс, пока не будут размещены все узлы или не будет обнаружен цикл (останутся узлы с ненулевой входящей степенью).

Вычисление входящих степеней

Сначала постройте список смежности и вычислите входящую степень (число входящих рёбер) каждого узла. Узлы с входящей степенью 0 являются начальными точками — у них нет зависимостей. Для графа с рёбрами [(0,1),(0,2),(1,3),(2,3)] входящие степени равны: 0→0, 1→1, 2→1, 3→2. Только узел 0 начинает с входящей степенью 0.

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

Реализация алгоритма Кана

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

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

Обнаружение циклов с помощью алгоритма Кана

Алгоритм Кана обеспечивает автоматическое обнаружение циклов: если len(order) < n, некоторые узлы так и не были добавлены в очередь, поскольку их входящая степень не стала равна 0, — они входят в цикл. Это проще, чем поддерживать массив посещённых узлов с цветовой маркировкой. Верните пустой список, чтобы сообщить о наличии цикла.

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

Временная и пространственная сложность

Алгоритм Кана обрабатывает каждый узел один раз (извлекает его из очереди один раз) и каждое ребро один раз (один раз уменьшает входящую степень). Временная сложность: O(V + E). Память: O(V + E) для списка смежности и массива входящих степеней плюс O(V) для очереди. Это оптимально: чтобы построить допустимый порядок, необходимо как минимум прочитать все узлы и рёбра.

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

Алгоритм Кана с мин-кучей вместо очереди создаёт лексикографически наименьший топологический порядок. Замените deque на heapq: добавляйте (node) и всегда сначала обрабатывайте наименьший доступный узел. Это гарантирует лексикографически наименьший допустимый порядок среди всех возможных топологических сортировок.

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

Применение: расписание курсов I

Расписание курсов (LeetCode 207): даны n курсов и предварительные условия; можно ли пройти все курсы? Представьте предварительные условия в виде ориентированных рёбер и проверьте, существует ли допустимая топологическая сортировка (то есть нет ли цикла). Верните истину, если алгоритм Кана создаёт порядок длины n, и ложь, если обнаружен цикл.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

Применение: расписание курсов II

Расписание курсов II (LeetCode 210): верните фактический порядок прохождения курсов. Действуйте так же, как выше, но верните список order, а не логическое значение. Если существует цикл, верните пустой список. В этом случае результат алгоритма Кана непосредственно используется как ответ.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

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

Более сложное применение: для задач с зависимостями найдите минимальное число «раундов», необходимое, если задачи без зависимостей могут выполняться параллельно. Обрабатывайте алгоритм Кана по уровням (аналогично обходу BFS по уровням): добавьте все узлы с нулевой входящей степенью в очередь, обработайте всю текущую очередь как один раунд, затем добавьте освободившиеся узлы для следующего раунда. Подсчитайте число раундов.

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

Топологическая сортировка и DP в DAG

Топологическая сортировка позволяет применять динамическое программирование в DAG: обрабатывайте узлы в топологическом порядке, и при вычислении dp[v] значения dp[u] всех предшественников уже будут окончательно вычислены. Это сочетает топологическую сортировку с DP в задачах поиска длиннейшего пути в DAG, минимальной стоимости достижения всех узлов или максимальной прибыли в цепочке зависимостей. Такой порядок гарантирует, что значение DP каждого узла будет вычислено ровно один раз после всех его зависимостей.

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

Быстрая проверка

Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы узнали: алгоритм Кана вычисляет топологическую сортировку, последовательно удаляя узлы с нулевой входящей степенью с помощью BFS, обнаружение циклов не требует дополнительных вычислений: если len(order) < n, существует цикл, а замена очереди на мин-кучу даёт лексикографически наименьший топологический порядок. Далее мы рассмотрим топологическую сортировку на основе постфиксного обхода DFS как альтернативу алгоритму Кана.

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

Урок «Алгоритм Кана: топологическая сортировка с помощью BFS» бесплатный?

Да — полный текст урока «Алгоритм Кана: топологическая сортировка с помощью BFS» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Алгоритм Кана: топологическая сортировка с помощью BFS»?

Вычислите полустепени захода всех вершин, добавьте вершины с нулевой полустепенью в очередь и обработайте очередь, чтобы получить топологический порядок и обнаружить циклы Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Алгоритм Кана: топологическая сортировка с помощью BFS»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Алгоритм Кана: топологическая сортировка с помощью BFS
  2. Топологическая сортировка DFS в порядке постобхода
  3. Расписание курсов I и II
  4. Компоненты сильной связности с алгоритмом Косарайю
← Назад к DSA Interview Prep