相关疑难解决方法(0)

如何从有向图中找到(迭代)有向图中的所有周期？

例如,我想要这样的东西:

A->B->A
A->B->C->A

但不是:B-> C-> B.

我需要一个工作算法来查找无向图中的所有简单循环.我知道成本可能是指数级的并且问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少.

经过长时间的研究(主要是在这里),我仍然没有工作方法.以下是我的搜索摘要:

查找无向图中的所有循环

无向图中的循环 - >仅检测是否存在循环

在无向图中查找多边形 - >非常好的描述,但没有解决方案

在有向图中查找所有循环 - >仅在有向图中查找循环

使用增强图库检测无向图中的循环

我发现的唯一一个解决我问题的答案是:

查找图表中的所有周期,redux

似乎找到一组基本的循环并对它们进行异或可以解决问题.找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...

我在编写一个算法时遇到了一些麻烦,该算法返回在无向图上形成简单循环的所有路径.

我首先考虑从顶点A开始的所有循环,对于下图

A,B,E,G,F
A,B,E,D,F
A,B,C,D,F
A,B,C,D,E,G,F

额外的周期将是

B,C,D,E
F,D,E,G

但是这些可以通过例如再次调用相同的算法但分别从B和D开始来找到.

该图如下所示 -

我目前的方法是通过访问A的所有邻居,然后访问邻居的邻居等来构建A的所有可能路径,同时遵循以下规则:

• 每次存在多个邻居时,就会找到一个分叉,并创建并探索来自A的新路径.
  

• 如果任何创建的路径访问原始顶点,则该路径是循环.
  

• 如果任何创建的路径访问相同的顶点两次(不同于A),则丢弃该路径.
  

• 继续,直到探索了所有可能的路径.

我目前在尝试避免不止一次发现相同的循环时遇到问题,我试图通过查看新邻居是否已经是另一个现有路径的一部分来解决这个问题,以便两个路径组合(如果是独立的)构建一个周期.

我的问题是:我是否遵循正确/更好/更简单的逻辑来解决这个问题.

我很感激你的意见