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 的大作中提到】
: 【 以下文字转载自 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 的大作中提到】
: a Hamiltonian path (or traceable path) is a path in an undirected graph
: which visits each vertex exactly once.
: 这跟我想找的相差太远了吧，随便一种cycle就行了，不需要经过每一个点（也不一定
: 有这样的cycle），而且我的是有向图，hamiltonian的是无向图。我只是想找出所有的
|
