Найдите все циклы в графике, возвращении

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

Я теперь хотел бы иметь некоторые предложения на том, могут ли все циклы в графике быть обнаружены через DFS и проверяющий на задние фронты?
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf (найденный здесь на S.O.) указывает один метод на основе оснований цикла. Меня лично, я не нахожу это очень интуитивным, таким образом, я ищу другое решение.

Править: Мое начальное мнение было, по-видимому, неправильным. S. затем отвечают "Идиотом".
Начальное мнение: Мое мнение - то, что это действительно могло проложить себе путь, поскольку ПОСЕЩЕНИЕ DFS (s. псевдокод DFS) недавно вводит каждый узел, который еще не посетили. В этом смысле каждая вершина показывает потенциальный запуск цикла. Кроме того, поскольку DFS посещает каждый край однажды, каждое граничное продвижение к начальной точке цикла также покрыто. Таким образом, при помощи DFS и заднего фронта, проверяющего его, должно действительно быть возможно обнаружить все циклы в графике. Обратите внимание, что, если циклы с различными числами участвующих узлов существуют (например, треугольники, прямоугольники и т.д.), дополнительная работа должна быть сделана для различения acutal "формы" каждого цикла.

7
задан Community 23 May 2017 в 12:09
поделиться

2 ответа

Если алгоритм обхода посещает каждое ребро только один раз, он не может найти все циклы. Ребро может быть частью нескольких циклов.

Кстати, что такое задний край?

Также, возможно, вам следует перефразировать / отформатировать свой вопрос. Это очень трудно читать.

0
ответ дан 7 December 2019 в 03:12
поделиться

Я уже подробно ответил на этот вопрос, поэтому проверьте это:

Будет ли источник- Сортировка по удалению всегда возвращает максимальный цикл?

Соответствующая часть ответа:

Выполните поиск в глубину на вашем график.

Вы хотите узнать ответ ребра, т. е. при обходе ребро что указывает на предка (в дерево DFS, которое индуцировано ребра посещаемых узлов для первого время) посещаемого узла. Для Например, если в стеке DFS есть узлы [A-> B-> C-> D] и пока вы исследуете D вы найдете край D-> B, это спина край. Каждый задний край определяет цикл.

Что еще более важно, циклы индуцировали по задним краям - это базовый набор циклы графа. "Базовый набор циклы »: вы можете построить все циклы графа только с помощью UNIONing и XORing циклы базового набора. Для Например, рассмотрим циклы [A1-> A2-> A3-> A1] и [A2-> B1-> B2-> B3-> A2]. Вы можете объединиться их в цикл: [A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1].

6
ответ дан 7 December 2019 в 03:12
поделиться
Другие вопросы по тегам:

Похожие вопросы: