Даст ли DFS от каждого узла все циклы в ориентированном графе

Question

Я хочу найти все циклы в ориентированном графе.Начиная поиск в глубину с одного узла, вы обнаружите несколько циклов (поиск по краям).Итак, я применил dfs ко всем узлам графа (то есть каждый раз, когда корень является другим узлом).Я могу получить все циклы, используя это (устраняя дубликаты).Но я не уверен, будет ли это работать для всех графиков и является ли это правильным подходом или нет.Может кто-нибудь подсказать мне, работает ли это во всех ситуациях.

Спасибо

Answer 1

Ответ НЕТ !Потому что запуск DFS на всех узлах указывает алгоритм полиномиального времени.И не существует алгоритма полиномиального времени, чтобы найти все циклы в ориентированном графе.

Рассмотрим такой случай. Предположим, у вас есть полный граф с n узлами (каждый узел указывает на все остальные узлы), тогда каждое непустое подмножество этих n узлов указывает цикл.Число таких подмножеств составляет 2 ^ n -1, поэтому невозможно найти экспоненциальное число циклов за полиномиальное время.

Answer 2

Если у вас отключены узлы (график не подключен), вам придется проходить по графику от каждого узла.Не имеет значения, используете ли вы DFS или BFS, так как вы не прекращаете свой обход при поиске определенного узла.

Я бы вел глобальный список VisitedNodes, чтобы вам не приходилось делать полные обходы из уже посещенныхузлы вместо вашего обычного списка предков "Per-Path", чтобы избежать циклов.