Поиск циклов в ориентированных графах
Раскрашивайте вершины, чтобы найти обратные рёбра
«Поиск циклов в ориентированных графах» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Почему циклы важны
Ориентированный цикл означает, что зависимости замыкаются сами на себя. Обнаружив цикл, вы понимаете, что топологический порядок или допустимое расписание создать невозможно.
Неориентированные графы устроены иначе
Здесь обнаружение цикла связано с направлением. Следование по рёбрам в неправильную сторону не считается, поэтому приёмы для неориентированных графов здесь не применимы.
Идея трёх цветов
Назначьте каждой вершине один из трёх цветов: белый означает, что вершина не посещена, серый — что она обрабатывается, чёрный — что полностью обработана.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nСерый означает, что вершина в стеке
Серая вершина находится на текущем пути DFS. Вы вошли в неё, но ещё не завершили исследование всех её потомков.
Войдите в вершину
Когда DFS достигает вершины, перед исследованием пометьте её серой. Так вы отмечаете её как часть текущего активного пути.
def dfs(u):
color[u] = GRAYСигнал обратного ребра
Если вы достигли соседа, который уже серый, значит, вы нашли обратное ребро в текущий путь. Это и есть цикл.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleРекурсивно обработайте белую вершину
Белый сосед ещё не исследован, поэтому выполните для него рекурсивный вызов. Сразу передайте наверх значение «истина», как только любой более глубокий вызов сообщит о цикле.
elif color[v] == WHITE and dfs(v):
return TrueЧёрный цвет означает безопасность
Чёрный сосед полностью исследован, и в нём нет циклов, поэтому его можно игнорировать. Повторное посещение лишь потратит время.
Завершите обработку вершины
После обработки всех соседей пометьте вершину чёрной. Она покидает активный путь и считается завершённой.
color[u] = BLACK
return FalseОхватите все компоненты
Граф может быть несвязным, поэтому запустите DFS из каждой ещё белой вершины, чтобы проверить весь граф.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Учитывайте предел рекурсии
Глубокие графы могут переполнить стек рекурсии Python. Увеличьте предел или перепишите DFS с явным стеком.
import sys
sys.setrecursionlimit(300000)Быстрая проверка
Во время DFS вы достигли соседа, который сейчас серый. Что вы только что обнаружили?
Итоги: обнаружение циклов
Раскрашивайте вершины в белый, серый, а затем чёрный цвет. Серый сосед во время DFS — это обратное ребро, доказывающее наличие ориентированного цикла. 🔁
Часто задаваемые вопросы
Урок «Поиск циклов в ориентированных графах» бесплатный?
Да — полный текст урока «Поиск циклов в ориентированных графах» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Поиск циклов в ориентированных графах»?
Раскрашивайте вершины, чтобы найти обратные рёбра Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Поиск циклов в ориентированных графах»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Топологическая сортировка алгоритмом Кана
- Поиск циклов в ориентированных графах
- Компоненты сильной связности
- Мосты и точки сочленения