在给定顶点坐标的图形中查找所有循环基础

Question

类似的问题发布在这里.

我有一个带有Vertex V和Edge 的无向图E.我正在寻找一种算法来识别该图中的所有循环基础.这种图表的一个例子如下所示:

现在,所有顶点坐标都是已知的(与上一个问题不同,与上图中的解释相反),因此可以找到包含整个图的最小周期.

在该图中,可能存在不形成任何循环的边.

这样做的最佳算法是什么？

这是另一个你可以看一看的例子:

假设这e1是首先被拾取的边缘,箭头显示边缘的方向.

Answer 1

我还没有尝试过这个，它相当贪婪，但应该有效：

1. 选择一个节点
2. 去邻居家
3. 继续前进，直到回到起始节点，但不允许您访问旧节点。
4. 如果您获得一个循环，如果它尚不存在或这些节点的子集构成了一个循环，请保存它。如果循环中的节点是另一个循环中节点的子集，则删除较大的循环（或者可能将其分成两部分？）
5. 从 2 点开始，与新邻居一起。
6. 使用新节点从 1 开始。

注释：在 3 处，您当然应该执行与步骤 2 相同的操作，因此采用所有可能的路径。

也许这就是一个开始？正如我所说，我还没有尝试过，所以它还没有优化。

编辑：可以在这里找到该算法的一种实现的未记录且未优化的版本： https: //gist.github.com/750015。但是，它并不能完全解决该问题，因为它只能识别“真实”子集。