g****t 发帖数: 31659 | 1 【 以下文字转载自 EE 讨论区 】
发信人: catccaatt (堕落是魔鬼), 信区: EE
标 题: 求助如何检测有向图里面所有的回路
发信站: BBS 未名空间站 (Sat Jan 16 20:15:37 2010, 美东)
就是cycle detection
最好有现成的source能直接用的,没有的话请告诉我有没有稍微快一点的方法,我直接
用C语言 深度搜索 尝试了只有200个点的数据跑了一晚上都没出来,是在没辙了。有其
他方法请告知,例子如图:
谢谢了 |
B****n 发帖数: 11290 | 2 這應該屬於圖論的東西 比方像Hamiltonian Cycle等
隨便一本圖論的書 就可以確定他要的是那種cycle
如果知道cycle的名字 用google搜尋一下 example:Hamiltonian Cycle code就可以找
到了 這些都有很多現成的code支持
【在 g****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 EE 讨论区 】 : 发信人: catccaatt (堕落是魔鬼), 信区: EE : 标 题: 求助如何检测有向图里面所有的回路 : 发信站: BBS 未名空间站 (Sat Jan 16 20:15:37 2010, 美东) : 就是cycle detection : 最好有现成的source能直接用的,没有的话请告诉我有没有稍微快一点的方法,我直接 : 用C语言 深度搜索 尝试了只有200个点的数据跑了一晚上都没出来,是在没辙了。有其 : 他方法请告知,例子如图: : 谢谢了
|
c*******t 发帖数: 1095 | 3 a Hamiltonian path (or traceable path) is a path in an undirected graph
which visits each vertex exactly once.
这跟我想找的相差太远了吧,随便一种cycle就行了,不需要经过每一个点(也不一定
有这样的cycle),而且我的是有向图,hamiltonian的是无向图。我只是想找出所有的 |
l******e 发帖数: 470 | 4 200个点的图里的cycle就有可能有非常非常多,exponential的
一晚上找不全也不奇怪
就找一个回路的话DFS,线性时间。
【在 c*******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a Hamiltonian path (or traceable path) is a path in an undirected graph : which visits each vertex exactly once. : 这跟我想找的相差太远了吧,随便一种cycle就行了,不需要经过每一个点(也不一定 : 有这样的cycle),而且我的是有向图,hamiltonian的是无向图。我只是想找出所有的
|