Обнаружение циклов в графе
Обнаружение циклов в графах чрезвычайно важно для понимания структуры и свойств данных в различных областях — например, при работе с зависимостями, обнаружении взаимоблокировок и маршрутизации в сетях. Выявляя циклы, мы можем предотвратить такие проблемы, как циклические зависимости, неэффективность и даже сбои в работе систем.
Для обнаружения цикла в графе можно использовать модифицированный алгоритм поиска в глубину (DFS).
Когда мы обходим граф с помощью DFS, мы обычно помечаем вершины как посещённые или непосещённые. Однако для обнаружения циклов этого недостаточно. Нужно использовать три состояния для каждой вершины:
- Вершина не посещена
- Вершина и её поддерево DFS находятся в процессе обработки
- Вершина полностью посещена (включая все дочерние вершины)
Таким образом, мы можем обнаружить цикл, если при обходе достигнем вершины, которая уже находится в состоянии обработки.
➰
Если при обходе мы находим вершину, помеченную как «в процессе обработки» (2), значит, в графе существует цикл.
Алгоритм будет работать по следующим шагам:
- Пометить все вершины как непосещённые
- Запустить DFS из какой-то вершины
- Для текущей вершины пометить её как «в процессе обработки»
- Когда все дочерние вершины текущей вершины обработаны, пометить её как полностью посещённую
Алгоритм подходит и для ориентированных, и для неориентированных графов:
color = [1] * n # цвет вершин (1: не посещена, 2: в процессе обработки, 3: полностью посещена)
def dfs(v, p): # поиск в глубину (v: вершина, p: родитель)
color[v] = 2 # пометить вершину как «в процессе обработки»
cycle = False # флаг для проверки наличия цикла
for to in g[v]: # для каждой вершины, смежной с v
if color[to] == 1: # если вершина не посещена
cycle |= dfs(to, v) # вызвать dfs для этой вершины и зафиксировать наличие цикла
elif color[to] == 2 and to != p: # если вершина «в процессе обработки» и это не родитель
cycle = True # установить флаг в True
color[v] = 3 # пометить вершину как полностью посещённую
return cycle # вернуть флаг
for start in range(n): # для каждой вершины
if color[start] == 1: # если вершина не посещена
if dfs(start, -1): # вызвать dfs для вершины и проверить наличие цикла
print('Cycle') # вывести «Cycle»
break # прервать цикл
else: # если цикл «for» не был прерван
print('No cycle') # вывести «No cycle»Обратите внимание, что в случае ориентированных графов учитывать родительскую вершину не требуется. Как вы думаете, почему? 🤔
Давайте проследим работу алгоритма на нескольких входных данных:
n = 4, e = 4
Входные пары
a, b следующие: [(0, 1), (0, 2), (1, 2), (3, 2)]Начальная вершина — 3
v=3, p=-1→color = [1, 1, 1, 2]⇒ исследуем все соседние вершины для 3 ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ исследуем все соседние вершины для 2 ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ исследуем все соседние вершины для 0 ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ исследуем все соседние вершины для 1 ⇒[0, 2]⇒ 0 помечена как 1 ⇒ устанавливаемcycle = True⇒return True
Задание: Проверить, содержит ли граф цикл
Дан ориентированный граф с
v вершинами и e рёбрами. Необходимо проверить, содержит ли граф цикл.Вход
Первая строка содержит два целых числа
v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).В следующих
e строках даны пары чисел v1, v2 (1 ≤ v1, v2 ≤ v), означающие, что из вершины v1 существует путь в вершину v2.Выход
Программа должна вывести
Yes, если в графе есть цикл, и No в противном случае.Примеры
Вход | Выход |
4 3
1 2
2 3
3 1
| Yes |
4 3
1 2
1 3
2 4 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB