算法 - 搜索网络拓扑中的所有环路

Question

我得到了由节点和链路定义的网络。我必须搜索网络中的所有环路。将不会给出节点的坐标。

是否有任何现有的算法或库可以做到这一点。或者你能否给我一些想法我可以解决这个问题？我在.NET中编程。

我画一个图来说明什么，我需要here

Answer 1

尝试Distance vector Routing.

该算法找到最短路径到所有其他节点的节点网络。

Answer 2

假设您的边缘没有被定向，并且节点之间存在最大的一条边，那么深度优先的生成树将覆盖所有节点并指示周期的哪里（这正是我认为你的意思是循环）将发生。我们使用这种算法来查找化学结构中的“环”。有许多语言许多实现 - 在这里是用一个小程序（http://oneweb.utc.edu/~Christopher-Mawata/petersen2/lesson20.htm）

Answer 3

的循环被称为cycles的教程，并this answer有很多信息给你的。