查找有向图中的所有循环

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

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

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

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

1> eminsenay..：

---

我在搜索中发现了这个页面,因为循环与强连接组件不同,我继续搜索,最后,我找到了一个有效的算法,列出了有向图的所有(基本)周期.它来自Donald B. Johnson,论文可以在以下链接中找到:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

可以在以下位置找到java实现:

http://normalisiert.de/code/java/elementaryCycles.zip

一个数学约翰逊的算法演示可以发现这里实现,可以从右边(下载"下载作者码").

注意:实际上,这个问题有很多算法.其中一些列在本文中:

http://dx.doi.org/10.1137/0205007

根据文章,约翰逊的算法是最快的算法.

---

对于任何使用python的人都要注意:Johnson算法在networkx中实现为`simple_cycle`.

---

@Gleno嗯,如果你的意思是你可以使用Tarjan来查找图中的所有周期而不是实现其余周期,那你就错了.[这里](http://upload.wikimedia.org/wikipedia/commons/5/5c/Scc.png"这里"),你可以看到强连接组件和所有周期之间的区别(循环cd和gh赢了'由Tarjan的alg)返回(@ batbrat你的混乱的答案也隐藏在这里:Tarjan的alg不会返回所有可能的循环,因此它的复杂性可能小于指数).Java代码可能更好,但它节省了我从文件中实现的努力.

---

@moteutsch:也许我错过了一些东西,但根据Johnson论文(和其他资料),如果没有顶点(除了开始/结束)出现不止一次,循环就是基本的.根据这个定义,是不是'A-> B-> C-> A`小学？

---

这个答案比选择的答案要好得多.我努力想弄清楚如何从强连接的组件中获得所有简单的循环,我挣扎了很长时间.事实证明这是非平凡的.约翰逊的论文包含了一个很好的算法,但是有点难以理解.我查看了Java实现,并在Matlab中进行了自己的实现.该代码可在https://gist.github.com/1260153获得.

2> Himadri Chou..：

---

使用回溯的深度优先搜索应该在这里工作.保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

如果您有一个邻接列表来表示图形,则DFS很容易实现.例如adj [A] = {B,C}表示B和C是A的子节点.

例如,下面的伪代码."start"是您从哪个节点开始的.

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

使用start节点调用上述函数:

visited = {}
dfs(adj,start,visited)

---

`if(node == start):` - 第一次调用中的`node和start`是什么

---

谢谢.我更喜欢这种方法,因为它很容易理解并且具有合理的时间复杂度,尽管可能不是最优的.

---

@ user1988876这似乎找到了涉及给定顶点的所有循环(这将是`start`).它从该顶点开始并执行DFS直到它再次返回到该顶点,然后它知道它找到了一个循环.但它实际上并没有输出周期,只是计算它们(但修改它来做而不应该太难).

3> Nikolay Ogny..：

---

首先 - 你真的不想尝试找到字面上的所有周期,因为如果有1那么就有无数个.例如ABA,ABABA等.或者可以将2个周期连接到8个周期等等......有意义的方法是寻找所有所谓的简单周期 - 那些不会跨越自己的周期在开始/结束点.然后,如果您希望您可以生成简单循环的组合.

在有向图中查找所有简单循环的基线算法之一是:在图中对所有简单路径(那些不自交的路径)进行深度优先遍历.每当当前节点在堆栈上具有后继节点时,就会发现一个简单的循环.它由堆栈中的元素组成,从标识的后继开始到堆栈顶部结束.所有简单路径的深度优先遍历类似于深度优先搜索,但是您不会将当前在堆栈上的访问节点标记/记录为停止点.

上面的强力算法非常低效,并且除此之外还生成多个循环副本.然而,它是多种实用算法的起点,它们应用各种增强功能以​​提高性能并避免循环重复.前一段时间我很惊讶地发现这些算法在教科书和网络上都不容易获得.所以我做了一些研究,并在开源Java库中的无向图中为循环实现了4个这样的算法和1个算法:http://code.google.com/p/niographs/.

顺便说一句,因为我提到了无向图:那些算法不同.构建生成树,然后不是树的一部分的每个边与树中的一些边形成一个简单的循环.发现这种循环形成了一个所谓的循环基础.然后可以通过组合2个或更多个不同的碱基循环来找到所有简单循环.有关详细信息,请参阅:http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf.

4> fernandosjp..：

---

我发现解决这个问题的最简单的选择是使用被调用的python lib networkx.

它实现了在这个问题的最佳答案中提到的约翰逊算法,但它的执行非常简单.

简而言之,您需要以下内容:

import networkx as nx
import matplotlib.pyplot as plt

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])

# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])

#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))

答案: [['a','b','d','e'],['a','b','c']]

5> Eran Medan..：

---

澄清:

强连接组件将查找其中至少有一个循环的所有子图,而不是图中所有可能的循环.例如,如果你采用所有强连接组件并将它们中的每一个折叠/分组/合并为一个节点(即每个组件的一个节点),你将获得一个没有循环的树(实际上是一个DAG).每个组件(基本上是一个至少有一个循环的子图)可以在内部包含更多可能的循环,因此SCC将找不到所有可能的循环,它将找到至少有一个循环的所有可能组,如果您组他们,然后图表将没有周期.

如同其他人提到的那样,在图中找到所有简单周期,约翰逊的算法是一个候选者.