PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 找四環有幾個，有沒有比O(n^3)快的算法

看板Prob_Solve (計算數學 Problem Solving)作者 (拍玄)時間7年前 (2017/08/23 00:17), 編輯推噓10(10推 0噓 12→)
留言22則, 4人參與, 最新討論串1/1
四環（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://www.ptt.cc/bbs/Prob_Solve/M.1503418629.A.400.html
推
08/23 01:25, , 1F
無向圖嗎? 有 O(n^2) 的算法
08/23 01:25, 1F
→
08/23 01:28, , 2F
對每個點 x, 以及每對 x 的鄰居 (y,z), A[y,z]++
08/23 01:28, 2F
→
08/23 01:29, , 3F
最後檢查有沒有某個 A[u,v] 的值大於 1
08/23 01:29, 3F
推
08/23 01:36, , 4F
如果圖的邊數不多的話有更外的算法
08/23 01:36, 4F
推
08/23 01:38, , 5F
08/23 01:38, 5F
→
08/23 01:38, , 6F
*快
08/23 01:38, 6F
推
08/23 02:10, , 7F
抱歉，上面的算法應改進成一發現某格值已為 1 而要加為 2
08/23 02:10, 7F
→
08/23 02:10, , 8F
時就要停下
08/23 02:10, 8F
→
08/23 02:11, , 9F
不然最糟時會是 O(n^3)...
08/23 02:11, 9F
→
08/23 07:41, , 10F
謝謝H大的回覆 我花點時間啃一下論文
08/23 07:41, 10F
推
08/23 08:05, , 11F
我之前有想過一個 O(n^2) 時間 O(n) 空間的方法
08/23 08:05, 11F
→
08/23 08:06, , 12F
不過只能偵測 4-cycle 存在而不是 counting
08/23 08:06, 12F
→
08/23 08:07, , 13F
從每個點作 BFS ，如果鄰居的鄰居有交集就是有4-cycle
08/23 08:07, 13F
→
08/23 08:07, , 14F
因為判斷鄰居的鄰居的交集頂多使用 O(n) 空間
08/23 08:07, 14F
→
08/23 08:07, , 15F
所以總共的時間複雜度是O(n^2) 空間複雜度是O(n)
08/23 08:07, 15F
推
08/23 08:51, , 16F
哎呀我沒有意識到原 po 需要的是計數不是存在性…上面的
08/23 08:51, 16F
→
08/23 08:51, , 17F
推文是存在與否的算法
08/23 08:51, 17F
推
08/23 08:58, , 18F
另外請問 a,c 或 b,d 可相同嗎？
08/23 08:58, 18F
推
08/23 08:58, , 19F
但是論文可以解 counting 吧 雖然需要矩陣乘法
08/23 08:58, 19F
推
08/23 09:01, , 20F
我指的是連結前面的那個
08/23 09:01, 20F
→
08/25 11:18, , 21F
了解 所以只需要要快一點的矩陣乘法就可以壓下去
08/25 11:18, 21F
推
08/28 19:41, , 22F
用矩陣乘法就算的出來了
08/28 19:41, 22F
‣ 更多 rareone 的文章
文章代碼(AID): #1Pd5a5G0 (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 rareone 的文章
文章代碼(AID): #1Pd5a5G0 (Prob_Solve)