Нахождение цикла в неориентированном графе против нахождения цикла в ориентированном графе
==========================================================================================

Итак, я читаю Алгоритмы Роберта Седжвика, 4-е изд. Книга и методы для нахождения цикла в ориентированном графе отличаются от методов для нахождения цикла в неориентированном графе.

Вот пример кода, чтобы найти цикл в неориентированном графе

Однако при попытке найти цикл в ориентированном графе Седжвик использует логический массив, в котором i-й элемент этого массива имеет значение true, если i-я вершина была проверена во время текущего стека вызовов. Для каждой проверенной вершины K мы проверяем, является ли K-й элемент логического массива истинным. Если это так, то у нас есть цикл. Мой вопрос: почему необходимо использовать этот логический массив для ориентированного графа. Не должен ли подход, который я только что перечислил, быть более эффективным с точки зрения памяти? И работает ли этот подход только для неориентированных графов? Зачем?

Вы не можете использовать один и тот же алгоритм. Приведенный выше алгоритм просто исследует все связанные компоненты графа. Если вы столкнулись с уже отмеченной вершиной, должно быть**two different paths** чтобы достичь его, и в**undirected graph there must be a cycle**, Если нет, вы можете перейти к следующему подключенному компоненту - не нужно очищать только что завершенный компонент.

С другой стороны, если у вас есть**directed graph**два разных пути к одной и той же вершине**don't make a cycle**, Таким образом, вам нужен другой алгоритм (например, вам может понадобиться очистить все шаги, которые вы отслеживаете).