Топологическая сортировка DFS в порядке постобхода
Выполните DFS и добавляйте каждую вершину в стек после полного обхода её соседей, затем извлеките вершины из стека, чтобы получить корректный топологический порядок
«Топологическая сортировка DFS в порядке постобхода» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Идея топологической сортировки на основе DFS
Второй классический алгоритм топологической сортировки использует DFS с обработкой в постпорядке. После полного обхода всех соседей вершины (и их потомков) поместите вершину в стек. Когда обработаны все вершины, извлеките элементы из стека, чтобы получить топологический порядок. Вершина, помещённая в стек после всех своих зависимостей, в обратном порядке окажется первой — поэтому обращённый постпорядок и есть топологическая сортировка.
Интуиция постпорядка
Рассмотрим граф зависимостей, в котором для прохождения курса A требуется курс B. Когда DFS посещает A, он сначала рекурсивно переходит к B. У B нет предварительных требований, поэтому обработка B завершается первой, и он первым помещается в стек. Затем завершается обработка A, и A также помещается в стек. Извлечение элементов из стека даёт в результате A перед B, но в конце мы меняем порядок и получаем B перед A: сначала пройти B, затем A. Постпорядок помещает зависимости в стек раньше зависящих от них вершин, поэтому обращённый стек образует корректный топологический порядок.
Трёхцветный DFS для обнаружения циклов
Используйте три состояния посещения: WHITE (0) = не посещена, GREY (1) = обрабатывается в данный момент (находится в стеке вызовов DFS), BLACK (2) = обработка полностью завершена. Обратное ребро — ребро к вершине GREY — указывает на наличие цикла. Рёбра к вершинам BLACK безопасны: они уже полностью исследованы. Эта трёхцветная схема корректно обнаруживает все циклы в ориентированных графах.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)Полная реализация топологической сортировки с DFS
Используйте рекурсивный DFS, который окрашивает вершины, помещает их в стек в постпорядке и возвращает ложное значение при обнаружении цикла. После посещения всех вершин обращённый стек содержит топологический порядок.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Итеративный DFS для предотвращения переполнения стека
Ограничение глубины рекурсии в языке программирования (по умолчанию 1000) может стать проблемой для больших графов. Итеративный DFS с явным стеком позволяет этого избежать. Приём заключается в следующем: сначала поместите в стек (node, False); извлекая элемент со значением False, поместите обратно (node, True) (это означает: «я вернусь сюда после обхода»), а затем поместите в стек всех ещё не посещённых соседей со значением False. При извлечении элемента со значением True окрасьте вершину в BLACK и поместите её в стек результата.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]Сравнение DFS и алгоритма Кана
Оба алгоритма работают за O(V + E). Основные различия: алгоритм Кана (BFS) естественным образом формирует вершины в порядке от самых ранних зависимостей и проще обнаруживает циклы — достаточно проверить длину результата. Постпорядок DFS работает рекурсивно и явно обнаруживает обратные рёбра. Алгоритм Кана предпочтительнее, если нужен результат в прямом порядке без последующего обращения. DFS предпочтительнее, если постпорядок нужен для других задач, например для обнаружения SCC. Оба подхода допустимы на собеседованиях.
Постпорядок в дереве и DAG
В дереве постпорядок посещает левое поддерево → правое поддерево → корень. В DAG постпорядок DFS посещает все зависимости вершины до обработки самой вершины — это та же идея, обобщённая на несколько предшественников и произвольную структуру графа. Корень дерева DFS (начальная вершина) помещается в стек после всех своих потомков, поэтому в обращённом стеке оказывается первым — это правильная топологическая позиция вершины без предшественников.
Инопланетный словарь (LeetCode 269)
Инопланетный словарь: дан отсортированный список слов на неизвестном языке, требуется вывести порядок символов. Сравните соседние слова посимвольно, чтобы найти первое различие — оно задаёт ребро c1 → c2, означающее, что c1 идёт перед c2. Соберите все такие рёбра и выполните топологическую сортировку, чтобы получить порядок символов неизвестного языка. Если существует цикл, порядок недействителен.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'Топологическая сортировка с ограничениями
В некоторых задачах требуется топологическая сортировка с дополнительными ограничениями, например сохранение относительного порядка элементов исходного списка. Объедините алгоритм Кана с настраиваемой очередью с приоритетами или предварительной сортировкой: сохраняйте исходный относительный порядок элементов, применяя стабильную сортировку содержимого очереди на каждом шаге. Такие варианты с ограничениями проверяют более глубокое понимание гибкости алгоритма.
Распознавание задач на топологическую сортировку
Фразы в задачах на собеседованиях, указывающие на топологическую сортировку: «даны зависимости», «предварительные требования», «порядок выполнения задач», «порядок сборки», «можно ли выполнить все задачи?», «найдите допустимую последовательность». Если задача требует упорядочить элементы так, чтобы одни шли раньше других, постройте ориентированный граф и примените топологическую сортировку алгоритмом Кана или DFS. Обнаружение циклов часто является дополнительным требованием той же задачи.
Сравнение результатов DFS и алгоритма Кана
DFS и алгоритм Кана могут построить разные допустимые топологические порядки для одного и того же графа. Оба результата правильны: у DAG может быть несколько допустимых топологических порядков. Чтобы проверить корректность, убедитесь, что для каждого ребра u → v в графе вершина u стоит раньше вершины v в результате. Если задача на собеседовании требует конкретный порядок, например лексикографически наименьший, используйте алгоритм Кана с минимальной кучей — постпорядок DFS естественным образом не даёт лексикографически наименьший порядок.
Быстрая проверка
Проверьте своё понимание концепций «Структуры данных & алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали, что топологическая сортировка с постпорядком DFS помещает вершины в стек после обхода всех их зависимостей, трёхцветная маркировка (WHITE/GREY/BLACK) обнаруживает циклы по обратным рёбрам к вершинам GREY, а обращение стека постпорядка даёт допустимый топологический порядок. Далее мы применим топологическую сортировку непосредственно к задачам «Расписание курсов I» и «Расписание курсов II».
Часто задаваемые вопросы
Урок «Топологическая сортировка DFS в порядке постобхода» бесплатный?
Да — полный текст урока «Топологическая сортировка DFS в порядке постобхода» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Топологическая сортировка DFS в порядке постобхода»?
Выполните DFS и добавляйте каждую вершину в стек после полного обхода её соседей, затем извлеките вершины из стека, чтобы получить корректный топологический порядок Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Топологическая сортировка DFS в порядке постобхода»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Алгоритм Кана: топологическая сортировка с помощью BFS
- Топологическая сортировка DFS в порядке постобхода
- Расписание курсов I и II
- Компоненты сильной связности с алгоритмом Косарайю