Я хочу подсчитать общее количество направленных циклов, доступных в ориентированном графе (требуется только подсчет).Подсчитайте количество циклов в ориентированном графе с использованием DFS
Вы можете предположить, что граф задан как матрица смежности.
Я знаю DFS, но не смог создать рабочий алгоритм для решения этой проблемы.
Просьба указать некоторый псевдокод, используя DFS.
Давайте рассмотрим, что мы раскрашиваем узлы тремя типами цветов. Если узел еще не обнаружен, его цвет будет белым. Если узел обнаружен, но любой из его потомков/еще не обнаружен, его цвет серый. В противном случае его цвет черный. Теперь, выполняя DFS, если мы сталкиваемся с ситуацией, когда есть граница между двумя серыми узлами, тогда график имеет цикл. Общее количество циклов будет общим числом раз, когда мы сталкиваемся с ситуацией, упомянутой выше, то есть мы находим ребро между двумя серыми узлами.
В глубине первый поиск каждого направленного края рассматривается только один раз, поэтому этот алгоритм дает количество циклов меньше числа ребер. К сожалению, может быть много циклов, чем ребер. Рассмотрим полный граф на n вершин. Каждое подмножество из двух или более вершин описывает по крайней мере один цикл [(n-1)! из них фактически], но имеет только n * (n-1) ребра, поэтому число циклов растет быстрее, чем 2^n, но число ребер не имеет. Таким образом, вышеуказанный алгоритм не может работать. – deinst
Не работает ли DFS для ациклических графиков ...? В противном случае вы просто продолжаете заниматься дайвингом и дайвингом навсегда. – Kevin