Алгоритм группировки всех циклов

Question

У меня много циклов (указано числовыми значениями, например, 1-2-3-4 соответствует циклу с 4 ребрами, ребро 1 равно {1:2}, ребро 2 равно {2:3}, ребро 3 равно {3,4}, ребро 4 равно {4,1} и т. Д.)

Говорят, что цикл связан с другим циклом, если они имеют одно и только одно ребро.

Например, допустим, у меня есть два цикла 1-2-3-4 и 5-6-7-8, тогда есть две группы циклов, потому что эти два цикла не связаны друг с другом. Если у меня есть два цикла 1-2-3-4 и 3-4-5-6, то у меня есть только одна группа циклов, потому что эти два цикла имеют одно и то же ребро.

Рисунок ниже должен проиллюстрировать мою точку зрения:

альтернативный текст http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

R1, R2 до R7 - это то, что я называю «циклом». На приведенном выше рисунке есть только одна группа циклов, охватывающая все от R1 до R7.

Какой самый эффективный способ найти все группы циклов?

Answer 1

Сначала найдите все циклы на графике и назовите их, например, A, B, C и т. Д. Теперь создайте новый график, в котором каждый найденный в графике цикл преобразуется в один узел в новом графике. Соедините узлы с ребром в новом графе, если соответствующие циклы «связаны» в старом графе, используя ваше (довольно необычное) определение подключенного.

Число «групп циклов» - это число подключенных компонентов в новом графике.

Answer 2

Я почти уверен, что это не самый эффективный способ, но это будет моя первая попытка:

Сначала поменяйте ребра вершинами. Итак, для ваших примеров циклов 1-2-3-4, 3-4-5-6 и 5-6-7-8 вам понадобится:

"12" => "A"
"23" => "B"
"34" => "C"
"45" => "D"
"56" => "E"
"67" => "F"
"78" => "G"
"41" => "H"
"63" => "I"
"85" => "J"

Это дает вам до (v * (v-1)) / 2 вершин, но хорошо - это может все же быть достаточно хорошо для алгоритма O (v ^ 2).

Затем представьте циклы как битовые поля: "1-2-3-4" становится ABCH

ABCDEFGHIJ
1110000100

и "3-4-5-6" становится CDEI

ABCDEFGHIJ
0011100010 

Таким образом, у них есть ровно один общий бит, что означает, что в исходном графе у них было ровно одно ребро. Это можно проверить либо побитово с помощью O (v ^ 2), либо с помощью двоичного поиска (сначала проверьте с помощью ANDing, если у них есть какой-либо общий бит, затем проверьте ANDing в первой половине бит и т.