作者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/cn.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