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

Question

有一个无向图，包含顶点V和边E。 我正在寻找一种算法来识别该图中的所有循环基。 以下是此类图形的示例：

现在，所有顶点坐标已知（与先前问题不同，并且与上图中的说明相反），因此可以找到囊括整个图形的最小循环。

在此图中，可能存在未形成任何循环的边。

最好的算法是什么？请参阅以下另一个示例：

假设e1是首选的边，并且箭头显示边缘的方向。

类似的问题可以在这里找到。

- Graviton

---

这是一个C#的问题吗？你可能可以找到任何解决你问题的通用算法。 - Tomas Jansson

更改我的别名...你找到解决方案了吗？我的建议算法对你有用吗？ - Tomas Jansson

Answer 1

我没有尝试过这个算法，它比较贪婪，但应该可以工作：

1. 选择一个节点。
2. 前往其中一个邻居节点。
3. 一直向前走，直到回到起始节点，但不能访问旧节点。
4. 如果得到一个循环，则保存它，如果它不存在或者是这些节点的子集构成的循环。如果循环中的节点是另一个循环中的节点的子集，则删除更大的循环（或者可能将其拆分为两个循环？）
5. 使用新的邻居节点重新开始第2步。
6. 使用新的节点重新开始第1步。

注释：在第3步中，当然应该像第2步一样做，因此要考虑所有可能的路径。

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

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

- Tomas Jansson

---

@Tomas，是的，我有。但是我有一个反例，我认为你的算法无法解决。 - Graviton

@Ngu：我的算法可能有问题。我在这里实现了算法或其某个版本：https://gist.github.com/750015。我的实现问题在于它不能过滤掉像节点1、2、3、4、5、6、7、8、9、13、15组成的大循环，因为该循环不是任何其他循环的真正超集。代码没有经过优化或注释，而且非常冗长，我直接从头写的。 - Tomas Jansson

@Ngu：我提供的解决方案可以给你所有“不同”的循环，你额外提供的例子对我的解决方案没有问题...但是我以为这是一个无向图？我在提供的链接中的实现已经更新了你的新例子，并且还包含了你的第一个例子，以及一个简单的例子展示了根据你的规范，我的解决方案失败的地方。如果你阅读我的代码，你会发现没有边，那是因为我不需要它们：）。我使用一个列表来连接节点，定义它们之间的连接关系。 - Tomas Jansson

@Ngu，真正的坐标是什么？节点没有任何坐标。然而，如果一个循环包含在另一个循环中，那么它肯定更难找到。 - Tomas Jansson

@Tomas，尽管没有显示坐标，但它们在我绘制节点的位置中得到了体现。 - Graviton