四環（4-cycle）
在圖上我們稱他<a,b,c,d,a>使得四個點a,b,c,d依序相鄰
我想問問大神存不存在比O(n^3)還快地找四環計數算法
算出一張simple graph上有幾個4-cycle
拜託了>_< 我想過judge

無向圖嗎? 有 O(n^2) 的算法對每個點 x, 以及每對 x 的鄰居 (y,z), A[y,z]++最後檢查有沒有某個 A[u,v] 的值大於 1如果圖的邊數不多的話有更外的算法http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf O(m^{4/3})*快抱歉，上面的算法應改進成一發現某格值已為 1 而要加為 2時就要停下不然最糟時會是 O(n^3)...

謝謝H大的回覆 我花點時間啃一下論文

我之前有想過一個 O(n^2) 時間 O(n) 空間的方法不過只能偵測 4-cycle 存在而不是 counting從每個點作 BFS ，如果鄰居的鄰居有交集就是有4-cycle因為判斷鄰居的鄰居的交集頂多使用 O(n) 空間所以總共的時間複雜度是O(n^2) 空間複雜度是O(n)

哎呀我沒有意識到原 po 需要的是計數不是存在性…上面的推文是存在與否的算法另外請問 a,c 或 b,d 可相同嗎？

但是論文可以解 counting 吧 雖然需要矩陣乘法

我指的是連結前面的那個

了解 所以只需要要快一點的矩陣乘法就可以壓下去

用矩陣乘法就算的出來了