Обнаружить циклы на графике

Возможный дубликат:
Поиск всех циклов на графике

Может ли кто-нибудь дать мне учебник, алгоритм ... для обнаружения циклов на графике?

Я нахожу несколько алгоритмов и реализую их, но не обнаруживаю все циклы

strong_connected_components_algorithm


graph algorithm graph-theory
person SajjadZare    schedule 01.03.2011    source источник
comment
Я думаю, что вопрос есть, хотя ответ на него неверен.   -  person CygnusX1    schedule 02.03.2011
comment
@Cygn Это не повод разрешать дубли. Просто зайдите туда и разогрейте вопрос, разместив комментарий, в котором говорится, что   -  person Dr. belisarius    schedule 02.03.2011
comment
Существует реализация для обнаружения всех циклов на графике в библиотеке python под названием networkx. Это действительно просто! Я дал подробный ответ в следующем сообщении: stackoverflow.com/questions/546655/finding-all-cycles-in-graph/   -  person fernandosjp    schedule 28.10.2016

Ответы (3)


arrow_upward
1
arrow_downward

С математической точки зрения:

Вход: График G = (V, E)

  1. Предположим, что ваш граф не является непересекающимся (между каждыми двумя вершинами существует путь)

  2. Вычислить остовное дерево T графа (для этого есть простые алгоритмы)

  3. Пусть E 'будет подмножеством E, которое не принадлежит остовному дереву T. Для каждого ребра e в E' его добавление к дереву создает ровно один цикл. Поместим все эти циклы в набор B.

  4. Мы определяем пространство двоичных циклов по циклам на вашем графике. В это пространство можно добавить два цикла. Сложение - это просто исключительная сумма по краям.

  5. Набор циклов B является «основой цикла». Любой другой цикл на вашем графике может быть сформирован как линейная комбинация циклов B.

Таким образом вы получите все возможные циклы на вашем графике.

Предупреждение: если ваш входной граф имеет v вершин и e ребер, то имеется 2 ^ (e - v +1) -1 разных циклов! Это довольно много - возможно, вы не захотите явно писать их все.

person CygnusX1    schedule 01.03.2011

arrow_upward
0
arrow_downward

BFS alg. тоже нормально. Я считаю, что это проще реализовать, чем DFS, поскольку он хранит посещаемые / посещаемые узлы в очереди. Проще проверить, были ли уже посещены определенные узлы.

person Andrei Duma    schedule 01.03.2011

arrow_upward
-2
arrow_downward

Я думаю, что DFS выполнит вашу работу, потому что мы отмечаем посещенный узел, и если мы снова найдем этот узел, есть цикл

person ashmish2    schedule 01.03.2011
comment
Такой подход неверен. Возьмем этот пример 1 -> 2 2 -> 3 1 -> 3 Теперь в этом случае мы выполняем dfs (1). Это приведет к вызову dfs (2) и отметке 2 как посещенных. Это вызовет dfs (3) и отметит 3 как посещенные. теперь dfs (3) снова будет вызываться из узла 1, и, поскольку он уже был посещен, вы неправильно сделаете вывод, что это цикл - person Purav Shah; 03.04.2012