在给定顶点坐标的情况下，在图形中查找所有循环基准 [英] Find All Cycle Bases In a Graph, With the Vertex Coordinates Given

问题描述

类似的问题在此处发布.

我有一个顶点为V和边为E的无向图.我正在寻找一种算法来标识该图中的所有循环基准.这样的图的示例如下所示:

I have an undirected graph with Vertex V and Edge E. I am looking for an algorithm to identify all the cycle bases in that graph. An example of such a graph is shown below:

现在，所有顶点坐标都是已知的( 与先前的问题 ，和不同，与上图)，因此可以找到涵盖整个图形的最小周期.

Now, all the vertex coordinates are known ( unlike previous question, and contrary to the explanation in the above diagram), therefore it is possible to find the smallest cycles that encompass the whole graph.

在此图中，可能有不形成任何循环的边.

In this graph, it is possible that there are edges that don't form any cycles.

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

What is the best algorithm to do this?

这是另一个示例，您可以看一下:

Here's another example that you can take a look at:

假定e1是首先被拾取的边缘，并且箭头显示了边缘的方向.

Assuming that e1 is the edge that gets picked first, and the arrow shows the direction of the edge.

推荐答案

我没有尝试过，它虽然很贪心，但应该可以工作:

I haven't tried this and it is rather greedy but should work:

1. 选择一个节点
2. 去找邻居的人
3. 继续前进，直到回到起始节点，但不允许您访问旧节点.
4. 如果获得一个循环，则将其保存(如果它不存在或这些节点的子集组成一个循环).如果循环中的节点是另一个循环中节点的子集，请删除较大的循环(或将其拆分为两个?)
5. 从2开始与新邻居结婚.
6. 从1开始有一个新节点.

评论:当然，在第3步，您应该执行与第2步相同的操作，因此请选择所有可能的路径.

Comments: At 3 you should of course do the same thing as for step 2, so take all possible paths.

也许这是一个开始?正如我说的，我还没有尝试过，所以没有进行优化.

Maybe that's a start? As I said, I haven't tried it so it is not optimized.

编辑:可以在此处找到该算法的一种实现的未记录且未经优化的版本:

An undocumented and not optimized version of one implementation of the algorithm can be found here: https://gist.github.com/750015. But, it doesn't solve the solution completely since it can only recognize "true" subsets.

这篇关于在给定顶点坐标的情况下，在图形中查找所有循环基准的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！