Обнаружение цикла в направленном графе

Question

Я прочитал дискуссию here, в SO о поиске цикла в ориентированном графе. Теперь, О.П. утверждает, что мы должны проверить две вещи:

1. Там в задний край от u к v
2. v находится в рекурсии стека

Почему нам нужен второй тест? Не могли бы вы привести пример, чтобы продемонстрировать его необходимость?

Answer 1

Ну, вы, вероятно, путались между определением заднего края в ориентированном графе и обратным краем на неориентированном графе. Да, они разные.

В то время как в неориентированный граф Задние края - это ребра от текущей вершины до уже посещенной вершины. (как указано в ссылке из вашей ссылки).
В ориентированный граф определение для заднего края отличается. Задний край в ориентированном графе - это ребро от текущей вершины до вершины GREY (DFS для этой вершины начата, но еще не закончена), что означает, что она все еще находится в стеке рекурсии.

Итак, если вы берете определение заднего края, как показано в ориентированном графе, то да, этого достаточно для обнаружения цикла.
Но если вы берете определение заднего края так, как оно есть на неориентированном графике, вам также необходимо убедиться, что v находится в стеке рекурсии, чтобы обнаружить цикл.

См. this и this для получения дополнительной информации и примеров.

Пример:
Рассмотрим порядок посещения DFS быть A -> B -> C.
В этом примере край <A,C> является обратным краем на графике (как уже было посещено C).
Но это не задний край в этом ориентированном графе - C уже был посещен, но не находится в стеке рекурсии, то есть это не цикл.

Answer 2

Недостаточно того факта, что мы уже посетили v. Это позволяет от u до v, но не от v до u.

Простые графические контрпример:

Число обход порядок. У нас есть задний край от 4 до 3, но у нас нет циклов.

Answer 3

Второй тест необходим, когда речь идет поперечного края, а не задний край. Перекрестный край относится к ребру, который идет от одной вершины к уже посещенному независимо от положения. A задний край относится к ребру, указывающему на предка стартовой вершины, которая все еще находится в рекурсивном стеке.С точки зрения того, как задавался вопрос, OP относится к заднему краю как кромке, которая указывает на другой уже посещенный край, но более точное объяснение будет перекрестным. Зная, что это задний край, достаточно, потому что он подразумевает второй шаг. Эти шаги требуются, когда первый является перекрестным краем, потому что второй доказывает, что поперечный край является задним краем. В ориентированном графе перекрестный ребро не всегда означает, что происходит цикл. Ниже приведен пример:

vertices a,b,c,d 
a->b 
a->c 
b->d 
d->c 

В зависимости от того, что это обрабатывается, d->c можно рассматривать как поперечное ребро, поэтому номер шага 2 потребовалось бы, чтобы обнаружить петлю. К сожалению, задняя кромка и перекрестье смешаны довольно часто, вызывая путаницу. Вот ссылка на другое описание разницы между ними, Depth-First Search.