Algorytm zgrupowanie wszystkich cyklach razem

Question

mam wiele cykli (wskazane przez wartości numerycznych, na przykład 1-2-3-4 odpowiada cyklowi, 4 krawędzi, krawędź 1 jest {1:2}, krawędź 2 jest {2:3}, krawędź 3 jest {3,4}, krawędź 4 to {4,1} itd.).

Mówi się, że cykl jest połączony z innym cyklem, jeśli mają one jedną i tylko jedną krawędź.

Na przykład, powiedzmy, że mam dwa cykle 1-2-3-4 i 5-6-7-8, to są dwie grupy cyklów, ponieważ te dwa cykle nie łączą się ze sobą. Jeśli mam dwa cykle: 1-2-3-4 i 3-4-5-6, to mam tylko jedną grupę cykli, ponieważ te dwa cykle mają tę samą krawędź.

Poniższy rysunek powinien być w stanie zilustrować mój punkt widzenia:

alt text http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

R1, R2 do R7 to, co nazywam "cykl". Na powyższym rysunku jest tylko jedna grupa cykli obejmująca wszystkie R1 do R7.

Jaki jest najbardziej skuteczny sposób na znalezienie wszystkich grup cyklów?

Answer 1

Najpierw znajdź wszystkie cykle na wykresie i oznacz je na przykład jako A, B, C itd. Teraz utwórz nowy wykres, w którym każdy cykl znaleziony na wykresie zostanie przekonwertowany na pojedynczy węzeł na nowym wykresie. Połącz węzły z krawędzią nowego wykresu, jeśli odpowiadające im cykle są "połączone" na starym wykresie, używając (raczej nietypowej) definicji połączonych.

Liczba "grup cykli" to liczba connected components na nowym wykresie.

Answer 2

jestem całkiem pewny, że nie jest to najbardziej skuteczny sposób, ale to będzie moja pierwsza próba:

Pierwsza wymiana ostrza o wierzchołkach: A więc na swoim przykładzie cykli 1-2-3-4, 3-4-5-6 i 5-6-7-8, ty „potrzeba ll:

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

daje ci do (V * (V-1))/2 wierzchołki, ale w porządku - to nadal może być wystarczająco dobre dla o (v^2) algorytmu.

Następnie przedstawiają cykle jak bitfields: "1-2-3-4" staje ABCH

ABCDEFGHIJ 
1110000100 

i "3-4-5-6" staje CDEI

ABCDEFGHIJ 
0011100010 

Tak mają dokładnie jeden wspólny mianownik, co oznacza, że ​​na oryginalnym wykresie mają wspólną jedną krawędź. Może to być sprawdzane krok po kroku za pomocą O (v^2) lub za pomocą wyszukiwania binarnego (pierwsze sprawdzenie za pomocą AND, jeśli mają jakiś wspólny bit, następnie sprawdź ANDING pierwszej połowy bitów itd.)