类似的问题发布在这里 https://stackoverflow.com/questions/1607124/algorithms-to-identify-all-the-cycle-bases-in-a-undirected-graph.
我有一个带有 Vertex 的无向图V和边缘E。我正在寻找一种算法来识别该图中的所有循环基础。此类图的示例如下所示：
现在，所有的顶点坐标都是known ( 与之前的问题不同, and与上图中的解释相反），因此可以找到包含整个图的最小循环。
在此图中，可能存在不形成任何循环的边。
执行此操作的最佳算法是什么？
这是您可以看一下的另一个示例：
假如说e1是最先被拾取的边，箭头显示边的方向。
我还没有尝试过这个，它相当贪婪，但应该有效：
- 选择一个节点
- 前往其邻居之一
- 继续前进，直到回到起始节点，但不允许访问旧节点。
- 如果您获得一个循环，如果它尚不存在或这些节点的子集构成了一个循环，请保存它。如果循环中的节点是另一个循环中节点的子集，则删除较大的循环（或者可能将其分成两部分？）
- 从 2 点开始，与新邻居一起。
- 使用新节点从 1 开始。
注释：在 3 处，您当然应该执行与步骤 2 相同的操作，因此采用所有可能的路径。
也许这就是一个开始？正如我所说，我还没有尝试过，所以它还没有优化。
EDIT:可以在此处找到该算法的一种实现的未记录且未优化的版本：https://gist.github.com/750015 https://gist.github.com/750015。但是，它并不能完全解决该问题，因为它只能识别“真实”子集。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
