检测循环有向图中的多个循环
我有一个有向循环图，其中包含多个循环，我需要一种方法来检测（并列出）有向图中存在的每个循环。
该图可以在这里看到： http://img412.imageshack.us/img412/3327 /schematic.gif
这是为了调试我的 python 脚本而放在一起的虚拟图。它包含循环：
[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]
该算法必须检测有向图中的每个循环，而不是只是最小的也不是它遇到的第一个。
I have a directed cyclic graph with more than one cycle in it and I need a way to detect (and list) each cycle present in the digraph.
The graph can be seen here: http://img412.imageshack.us/img412/3327/schematic.gif
This is a dummy graph put together for the sake of debugging my python script. It contains the cycles:
[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]
The algorithm must detect every cycle in the digraph, not just the smallest nor the first it encounters.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您并没有真正指定如何表示有向图，但您可以查看 Neopythonic：检测有向图中的循环。
You didn't really specify how you represent the Directed graph, but you can have a look at Neopythonic:Detecting Cycles in directed graph.
AFAIK，python-graph 只找到一个循环，而不是所有可能的循环。请参阅：
http://groups.google.com/group/python-graph /browse_thread/thread/9170926f1bdd097b
另一篇文章似乎解决了这个问题中提出的问题：
http://www.bitformation.com/art/python_toposort.html
它使用 RE Tarjan 于 1972 年设计的算法
AFAIK, python-graph only finds one cycle, not all posible cycles. See:
http://groups.google.com/group/python-graph/browse_thread/thread/9170926f1bdd097b
This other article seems to solve the problem presented in this question:
http://www.bitformation.com/art/python_toposort.html
It's using the algorithm devised by R. E. Tarjan in 1972
您可能想尝试使用此库。它有一个循环检测算法。
You might want to try and use this library. It has a cycle detection algorithm.