Алгоритм для собирания в группу всех циклов
У меня есть много циклов (обозначенный числовыми значениями, например, 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, затем у меня есть только одна группа цикла, потому что эти два цикла совместно используют тот же край.
Число ниже должно смочь проиллюстрировать мой тезис:
R1, R2 кому: R7 то, что я называю "циклом". В вышеупомянутом числе существует только одна группа цикла, охватывающая весь R1 кому: R7.
Что самый эффективный путь состоит в том, чтобы найти всеми группами цикла?
2 ответа
Сначала найдите все циклы на графике и пометьте их, например, A, B, C и т. д. Теперь создайте новый граф, в котором каждый цикл, найденный в графе, преобразуется в единственный узел в новом графе. Соедините узлы с ребром в новом графе, если соответствующие циклы «связаны» в старом графе, используя ваше (довольно необычное) определение связности.
Количество «групп циклов» - это количество компонентов связности в новом графе.
Я почти уверен, что это не самый эффективный способ, но это была бы моя первая попытка:
Первый обмен ребрами вершинами: Итак, для вашего примера циклы 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), либо с помощью двоичного поиска (сначала проверьте с помощью AND, если у них есть какие-либо общие биты, затем проверьте AND с первой половиной бит и т. Д.)
{{ 1}}