Thuật toán cho Tập đoàn Tất cả các Cycles Cùng

Question

Tôi có rất nhiều chu kỳ (thể hiện bằng giá trị số, ví dụ, 1-2-3-4 tương ứng với một chu kỳ, với 4 cạnh, mép 1 là {1:2}, cạnh 2 là {2:3}, cạnh 3 là {3,4}, cạnh 4 là {4,1}, v.v.).

Chu kỳ được cho là được kết nối với một chu kỳ khác nếu chúng chia sẻ một và chỉ một cạnh. Ví dụ: giả sử tôi có hai chu kỳ 1-2-3-4 và 5-6-7-8, thì có hai nhóm chu kỳ vì hai chu kỳ này không kết nối với nhau. Nếu tôi có hai chu kỳ 1-2-3-4 và 3-4-5-6, thì tôi chỉ có một nhóm chu kỳ vì hai chu kỳ này chia sẻ cùng một cạnh.

Hình bên dưới sẽ có thể để minh họa cho quan điểm của tôi:

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

Các R1, R2-R7 là những gì tôi gọi là "chu kỳ". Trong hình trên, chỉ có một nhóm chu kỳ bao gồm tất cả các R1 đến R7.

Cách hiệu quả nhất để tìm tất cả các nhóm chu kỳ là gì?

Answer 1

Đầu tiên tìm tất cả các chu kỳ trong biểu đồ và gắn nhãn cho chúng ví dụ A, B, C, v.v. Bây giờ, hãy tạo một biểu đồ mới trong đó mỗi chu kỳ được tìm thấy trong biểu đồ được chuyển đổi thành một nút trong biểu đồ mới. Tham gia các nút với một cạnh trong biểu đồ mới nếu các chu kỳ tương ứng được "kết nối" trong biểu đồ cũ, sử dụng định nghĩa của bạn (không bình thường) được kết nối.

Số lượng "nhóm chu kỳ" sau đó là số lượng connected components trong biểu đồ mới.

Answer 2

Tôi khá chắc chắn, rằng đây không phải là cách hiệu quả nhất, nhưng điều này sẽ nỗ lực ban đầu của tôi:

trao đổi đầu tiên cạnh với đỉnh: Vì vậy, ví dụ chu kỳ của bạn 1-2-3-4, 3-4-5-6 và 5-6-7-8, bạn sẽ cần:

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

Điều này cho phép bạn (v * (v-1))/2 đỉnh, nhưng không sao - nó vẫn có thể đủ tốt cho thuật toán O (v^2).

Sau đó, đại diện cho các chu kỳ như bitfields: "1-2-3-4" trở thành ABCH

ABCDEFGHIJ 
1110000100 

và "3-4-5-6" trở thành CDEI

ABCDEFGHIJ 
0011100010 

Vì vậy, họ có chính xác một điểm chung, có nghĩa là trong biểu đồ ban đầu, họ có chính xác một cạnh chung. Điều này có thể được kiểm tra từng chút một với O (v^2), hoặc với tìm kiếm nhị phân (kiểm tra đầu tiên bởi ANDing, nếu chúng có điểm chung, sau đó kiểm tra VÀO nửa đầu tiên của bit, v.v.)