graph - 在给定顶点坐标的情况下，在图中查找所有圈基

Question

一个类似的问题 is posted here .

我有一个带顶点的无向图 V和边缘 E .我正在寻找一种算法来识别该图中的所有循环基数。此类图的示例如下所示:



现在，所有的顶点坐标都是已知的( 与之前的问题 不同，与上图中的解释相反)，因此可以找到包含整个图的最小循环。

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

执行此操作的最佳算法是什么？

这是您可以查看的另一个示例:



假设 e1是最先被拾取的边，箭头表示边的方向。

Answer 1

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

选取一个节点

去邻居家

继续前进，直到回到起始节点，但不允许访问旧节点。

如果你得到一个循环，如果它不存在或者这些节点的一个子集组成一个循环，就保存它。如果循环中的节点是另一个循环中节点的子集，则删除较大的循环(或者可能将其分成两部分？)

与新邻居从 2 点重新开始。

使用新节点从 1 开始。

评论:在 3 时，您当然应该执行与步骤 2 相同的操作，因此采用所有可能的路径。

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

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