作者rareone (拍玄)
看板Prob_Solve
標題[問題] 找四環有幾個，有沒有比O(n^3)快的算法
時間Wed Aug 23 00:17:04 2017
四環（4-cycle）
在圖上我們稱他<a,b,c,d,a>使得四個點a,b,c,d依序相鄰
我想問問大神存不存在比O(n^3)還快地找四環計數算法
算出一張simple graph上有幾個4-cycle
拜託了>_< 我想過judge
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.207.24
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1503418629.A.400.html
1F：推 hcsoso: 無向圖嗎? 有 O(n^2) 的算法 08/23 01:25
2F：→ hcsoso: 對每個點 x, 以及每對 x 的鄰居 (y,z), A[y,z]++ 08/23 01:28
3F：→ hcsoso: 最後檢查有沒有某個 A[u,v] 的值大於 1 08/23 01:29
4F：推 hcsoso: 如果圖的邊數不多的話有更外的算法 08/23 01:36
6F：→ hcsoso: *快 08/23 01:38
7F：推 hcsoso: 抱歉，上面的算法應改進成一發現某格值已為 1 而要加為 2 08/23 02:10
8F：→ hcsoso: 時就要停下 08/23 02:10
9F：→ hcsoso: 不然最糟時會是 O(n^3)... 08/23 02:11
10F：→ rareone: 謝謝H大的回覆 我花點時間啃一下論文 08/23 07:41
11F：推 FRAXIS: 我之前有想過一個 O(n^2) 時間 O(n) 空間的方法 08/23 08:05
12F：→ FRAXIS: 不過只能偵測 4-cycle 存在而不是 counting 08/23 08:06
13F：→ FRAXIS: 從每個點作 BFS ，如果鄰居的鄰居有交集就是有4-cycle 08/23 08:07
14F：→ FRAXIS: 因為判斷鄰居的鄰居的交集頂多使用 O(n) 空間 08/23 08:07
15F：→ FRAXIS: 所以總共的時間複雜度是O(n^2) 空間複雜度是O(n) 08/23 08:07
16F：推 hcsoso: 哎呀我沒有意識到原 po 需要的是計數不是存在性…上面的 08/23 08:51
17F：→ hcsoso: 推文是存在與否的算法 08/23 08:51
18F：推 hcsoso: 另外請問 a,c 或 b,d 可相同嗎？ 08/23 08:58
19F：推 FRAXIS: 但是論文可以解 counting 吧 雖然需要矩陣乘法 08/23 08:58
20F：推 hcsoso: 我指的是連結前面的那個 08/23 09:01
21F：→ rareone: 了解 所以只需要要快一點的矩陣乘法就可以壓下去 08/25 11:18
22F：推 firejox: 用矩陣乘法就算的出來了 08/28 19:41