在有向图中查找所有的周期

我如何find（迭代）有向图中所有的周期从/到给定的节点？

例如，我想要这样的东西：

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

但不是：B-> C-> B

Answer 1

我在我的search中find了这个页面，由于循环与强连通的组件不一样，我继续search，最后find了一个有效的algorithm，列出了有向图的所有（基本）循环。 它来自唐纳德·B·约翰逊，文章可以在以下链接中find：

comp/150GA/homeworks/hw1/Johnson75.PDF

一个java实现可以在下面find：

code/java/elementaryCycles.zip

约翰逊algorithm的Mathematica演示可以在这里find，实现可以从右边下载 （ “下载作者代码” ）。

注意：实际上，这个问题有很多algorithm。 其中一些在本文中列出：

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

根据文章，约翰逊的algorithm是最快的。

Answer 2

深度首先search回溯应该在这里工作。 保持一个布尔值数组来跟踪你之前是否访问过一个节点。 如果你用完了新的节点（没有击中已经存在的节点），那么只需要回溯并尝试一个不同的分支。

如果您有一个邻接表来表示图，那么DFS很容易实现。 例如adj [A] = {B，C}表示B和C是A的孩子。

例如，下面的伪代码。 “开始”是您开始的节点。

 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; 

用起始节点调用上面的函数：

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

Answer 3

首先 – 你不是真的想试图从字面上find所有的循环，因为如果有1个，那么就有无数的循环。 例如ABA，ABABA等。或者可以将2个周期连接成8个循环等等。有意义的方法是寻找所谓的简单循环 – 那些除了自身之外不交叉的循环在开始/结束点。 那么如果你愿意，你可以产生简单的周期组合。

在有向图中查找所有简单循环的基准algorithm之一是：在图中对所有简单path（不自己交叉的）进行深度优先遍历。 每当当前节点在栈上有一个后继，就会发现一个简单的循环。 它由堆栈上的元素组成，以标识的后继者开始，以堆栈顶部结束。 所有简单path的深度优先遍历与深度优先search相似，但是除了当前堆栈中的那些被访问的节点不作为停止点标记/logging。

上面的蛮力algorithm是非常低效的，除此之外还产生多个周期的副本。 然而，这是多种实用algorithm的出发点，它们应用各种增强function来提高性能并避免循环复制。 我很惊讶地发现，这些algorithm在教科书和networking上都不是很容易find。 所以我做了一些研究，在一个开放源代码的Java库中实现了4个这样的algorithm和1个无向图中的循环algorithm： http ： //code.google.com/p/niographs/ 。

顺便说一句，因为我提到无向图：这些algorithm是不同的。 构build一棵生成树，然后每个不是树的一部分的边与树中的一些边形成一个简单的循环。 这种循环形成了一个所谓的循环基础。 所有简单的循环可以通过组合2个或更多个不同的基本循环来find。 欲了解更多详情，请参阅例如： http : //dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf 。

Answer 4

我发现解决这个问题最简单的select是使用名为networkx的python库。

它实现了在这个问题的最佳答案中提到的约翰逊algorithm，但它执行起来相当简单。

总之你需要以下几点：

 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']]

Answer 5

澄清：

1. 强连通组件将查找至less有一个周期的所有子图，而不是图中所有可能的周期。 例如，如果将所有强连通的组件合并，并将它们中的每一个合并到一个节点（即每个组件的节点），则会得到一个没有周期的树（实际上是一个DAG）。 每个组件（基本上是一个至less有一个周期的子图）在内部可以包含更多的可能的周期，所以SCC将不会find所有可能的周期，它将find所有可能的组，至less有一个周期，如果组他们，那么图表将不会有周期。

2. 像其他人提到的那样，在图中find所有简单的循环，约翰逊的algorithm是一个候选人。

Answer 6

我曾经作为一个面试问题给过这个问题，我怀疑这件事发生在你身上，你是来这里寻求帮助的。 把问题分解成三个问题就变得简单了。

1. 你如何确定下一个有效的路线
2. 你如何确定一个点是否已被使用
3. 你怎么避免再次跨越同一点

问题1）使用迭代器模式提供迭代路由结果的方法。 把逻辑放到下一个路线的好地方可能就是迭代器的“moveNext”了。 要find一个有效的路线，这取决于你的数据结构。 对我来说，这是一个充满了有效的路线可能性的SQL表，所以我不得不build立一个查询来获得给定的源有效的目的地。

问题2）当你find它们的时候，将每个节点推到一个集合中，这意味着通过询问你正在build立的集合，你可以很容易地看到你是否“倍增”了一个点。

问题3）如果在任何时候你看到你正在翻倍，你可以从集合中popup东西并“备份”。 然后从那一点开始尝试再次“前进”。

Hack：如果您使用的是Sql Server 2008，那么您可以使用一些新的“层次结构”来快速解决这个问题，如果您在树中构build数据。

Answer 7

从节点X开始，检查所有的子节点（父节点和子节点是否相同，如果是无向的）。 将这些子节点标记为X的子节点。从任何这样的子节点A，将它标记为A，X'的子节点，其中X'标记为2步。 如果以后按X并将其标记为X的子项，则表示X处于3节点循环中。 回溯到它的父母很容易（因为，algorithm不支持这个，所以你会发现任何父母有X'）。

注意：如果graphics是无向的或者有任何双向的边缘，这个algorithm变得更加复杂，假设你不想在一个周期内两次遍历相同的边缘。

Answer 8

在DAG中查找所有周期涉及两个步骤（algorithm）。

第一步是使用Tarjan的algorithm来find一组强连通的组件。

1. 从任意的顶点开始。
2. 来自该顶点的DFS。 对于每个节点x，保留两个数字，dfs_index [x]和dfs_lowval [x]。 dfs_index [x]在该节点被访问时存储，而dfs_lowval [x] = min（dfs_low [k]），其中k是x的所有孩子，而不是dfs生成树中x的直接父亲。
3. 所有具有相同dfs_lowval [x]的节点都位于相同的强连接组件中。

第二步是在连接的组件中查找循环（​​path）。 我的build议是使用Hierholzeralgorithm的修改版本。

这个想法是：

1. select任何起始顶点v，然后沿着从该顶点开始的一条边，直到返回到v。由于所有顶点的偶数度确保当轨迹进入另一个顶点时，不可能卡住v以外的任何顶点顶点w必须有一个未使用的边离开w。 以这种方式形成的巡视是闭合的巡视，但是可能不包括初始graphics的所有顶点和边缘。
2. 只要存在一个属于当前巡视的顶点v，但是它的相邻边不属于巡视的一部分，则从v开始另一个巡视，沿着未使用的边，直到返回到v，并将以这种方式形成的巡视join到以前的旅游。

下面是一个带有testing用例的Java实现的链接：

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

Answer 9

在无向图的情况下，最近发表的论文（ 无向图中的循环和stpath的最优列表 ）提供了渐近最优解。 你可以在这里阅读它http://arxiv.org/abs/1205.2766或在这里http://dl.acm.org/citation.cfm?id=2627951我知道它不回答你的问题，但自你的问题没有提到方向，它可能仍然是有用的谷歌search

Answer 10

如果你想要在图中find所有的基本电路，你可以使用1970年以来由JAMES C. TIERNAN在一篇论文中发现的ECalgorithm。

非常原始的 ECalgorithm，我设法在PHP中实现它（希望没有错误显示在下面）。 如果有的话，它也可以find循环。 这个实现中的电路（试图克隆原始电路）是非零元素。 零这里代表不存在（null，因为我们知道它）。

除此之外，下面的其他实现使得algorithm更独立，这意味着节点可以从任何地方开始，甚至从负数开始，例如-4，-3，-2等等。

在这两种情况下，都要求节点是连续的。

您可能需要学习原始论文James C. Tiernan基础电路algorithm

 <?php echo "<pre><br><br>"; $G = array( 1=>array(1,2,3), 2=>array(1,2,3), 3=>array(1,2,3) ); define('N',key(array_slice($G, -1, 1, true))); $P = array(1=>0,2=>0,3=>0,4=>0,5=>0); $H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P ); $k = 1; $P[$k] = key($G); $Circ = array(); #[Path Extension] EC2_Path_Extension: foreach($G[$P[$k]] as $j => $child ){ if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){ $k++; $P[$k] = $child; goto EC2_Path_Extension; } } #[EC3 Circuit Confirmation] if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle $Circ[] = $P; } #[EC4 Vertex Closure] if($k===1){ goto EC5_Advance_Initial_Vertex; } //afou den ksana theoreitai einai asfales na svisoume for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N if( $H[$P[$k-1]][$m]===0 ){ $H[$P[$k-1]][$m]=$P[$k]; break(1); } } for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N $H[$P[$k]][$m]=0; } $P[$k]=0; $k--; goto EC2_Path_Extension; #[EC5 Advance Initial Vertex] EC5_Advance_Initial_Vertex: if($P[1] === N){ goto EC6_Terminate; } $P[1]++; $k=1; $H=array( 1=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 2=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 3=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 4=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 5=>array(1=>0,2=>0,3=>0,4=>0,5=>0) ); goto EC2_Path_Extension; #[EC5 Advance Initial Vertex] EC6_Terminate: print_r($Circ); ?> 

那么这是另一个实现，更独立的图，没有转到和没有数组值，而是它使用数组键，path，graphics和电路存储为数组键（如果你喜欢使用数组值，只需更改所需线）。 示例图从-4开始显示其独立性。

 <?php $G = array( -4=>array(-4=>true,-3=>true,-2=>true), -3=>array(-4=>true,-3=>true,-2=>true), -2=>array(-4=>true,-3=>true,-2=>true) ); $C = array(); EC($G,$C); echo "<pre>"; print_r($C); function EC($G, &$C){ $CNST_not_closed = false; // this flag indicates no closure $CNST_closed = true; // this flag indicates closure // define the state where there is no closures for some node $tmp_first_node = key($G); // first node = first key $tmp_last_node = $tmp_first_node-1+count($G); // last node = last key $CNST_closure_reset = array(); for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){ $CNST_closure_reset[$k] = $CNST_not_closed; } // define the state where there is no closure for all nodes for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){ $H[$k] = $CNST_closure_reset; // Key in the closure arrays represent nodes } unset($tmp_first_node); unset($tmp_last_node); # Start algorithm foreach($G as $init_node => $children){#[Jump to initial node set] #[Initial Node Set] $P = array(); // declare at starup, remove the old $init_node from path on loop $P[$init_node]=true; // the first key in P is always the new initial node $k=$init_node; // update the current node // On loop H[old_init_node] is not cleared cause is never checked again do{#Path 1,3,7,4 jump here to extend father 7 do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6 $new_expansion = false; foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6 if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){ $P[$child]=true; // add this child to the path $k = $child; // update the current node $new_expansion=true;// set the flag for expanding the child of k break(1); // we are done, one child at a time } } }while(($new_expansion===true));// Do while a new child has been added to the path # If the first node is child of the last we have a circuit if( isset($G[$k][$init_node])===true ){ $C[] = $P; // Leaving this out of closure will catch loops to } # Closure if($k>$init_node){ //if k>init_node then alwaya count(P)>1, so proceed to closure $new_expansion=true; // $new_expansion is never true, set true to expand father of k unset($P[$k]); // remove k from path end($P); $k_father = key($P); // get father of k $H[$k_father][$k]=$CNST_closed; // mark k as closed $H[$k] = $CNST_closure_reset; // reset k closure $k = $k_father; // update k } } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k; // Advance Initial Vertex Context }//foreach initial }//function ?> 

我已经分析并logging了欧共体，但不幸的是文件是用希腊文写成的。

Answer 11

~bard/IP/Handouts/cycles.html

Answer 12

我偶然发现了一个似乎比Johnsonalgorithm更有效的algorithm（至less对于更大的图）。 然而，我不确定它的性能与Tarjan的algorithm相比。
另外，到目前为止我只检查了三angular形。 如果感兴趣的话，请参阅千叶千叶和西尾高雄（ http://dx.doi.org/10.1137/0214017 ）的“Arboricity和Subgraph Listing Algorithms”

Answer 13

你不能做一个小的recursion函数来遍历节点吗？

 readDiGraph( string pathSoFar, Node x) { if(NoChildren) MasterList.add( pathsofar + Node.name ) ; foreach( child ) { readDiGraph( pathsofar + "->" + this.name, child) } } 

如果你有大量的节点，你将用完堆栈

Answer 14

Javascript解决scheme使用不相交集链接列表。 可以升级到脱节设置的森林，以加快运行时间。

 var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY' console.log(input); //above solution should be 3 because the components are //{0,1,2}, because {0,1} and {1,2} therefore {0,1,2} //{3} //{4} //MIT license, authored by Ling Qing Meng //'4\nYYNN\nYYYN\nNYYN\nNNNY' //Read Input, preformatting var reformat = input.split(/\n/); var N = reformat[0]; var adjMatrix = []; for (var i = 1; i < reformat.length; i++) { adjMatrix.push(reformat[i]); } //for (each person x from 1 to N) CREATE-SET(x) var sets = []; for (var i = 0; i < N; i++) { var s = new LinkedList(); s.add(i); sets.push(s); } //populate friend potentials using combinatorics, then filters var people = []; var friends = []; for (var i = 0; i < N; i++) { people.push(i); } var potentialFriends = k_combinations(people,2); for (var i = 0; i < potentialFriends.length; i++){ if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){ friends.push(potentialFriends[i]); } } //for (each pair of friends (xy) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y) for (var i = 0; i < friends.length; i++) { var x = friends[i][0]; var y = friends[i][1]; if (FindSet(x) != FindSet(y)) { sets.push(MergeSet(x,y)); } } for (var i = 0; i < sets.length; i++) { //sets[i].traverse(); } console.log('How many distinct connected components?',sets.length); //Linked List data structures neccesary for above to work function Node(){ this.data = null; this.next = null; } function LinkedList(){ this.head = null; this.tail = null; this.size = 0; // Add node to the end this.add = function(data){ var node = new Node(); node.data = data; if (this.head == null){ this.head = node; this.tail = node; } else { this.tail.next = node; this.tail = node; } this.size++; }; this.contains = function(data) { if (this.head.data === data) return this; var next = this.head.next; while (next !== null) { if (next.data === data) { return this; } next = next.next; } return null; }; this.traverse = function() { var current = this.head; var toPrint = ''; while (current !== null) { //callback.call(this, current); put callback as an argument to top function toPrint += current.data.toString() + ' '; current = current.next; } console.log('list data: ',toPrint); } this.merge = function(list) { var current = this.head; var next = current.next; while (next !== null) { current = next; next = next.next; } current.next = list.head; this.size += list.size; return this; }; this.reverse = function() { if (this.head == null) return; if (this.head.next == null) return; var currentNode = this.head; var nextNode = this.head.next; var prevNode = this.head; this.head.next = null; while (nextNode != null) { currentNode = nextNode; nextNode = currentNode.next; currentNode.next = prevNode; prevNode = currentNode; } this.head = currentNode; return this; } } /** * GENERAL HELPER FUNCTIONS */ function FindSet(x) { for (var i = 0; i < sets.length; i++){ if (sets[i].contains(x) != null) { return sets[i].contains(x); } } return null; } function MergeSet(x,y) { var listA,listB; for (var i = 0; i < sets.length; i++){ if (sets[i].contains(x) != null) { listA = sets[i].contains(x); sets.splice(i,1); } } for (var i = 0; i < sets.length; i++) { if (sets[i].contains(y) != null) { listB = sets[i].contains(y); sets.splice(i,1); } } var res = MergeLists(listA,listB); return res; } function MergeLists(listA, listB) { var listC = new LinkedList(); listA.merge(listB); listC = listA; return listC; } //access matrix by i,j -> returns 'Y' or 'N' function isFriend(matrix, pair){ return matrix[pair[0]].charAt(pair[1]); } function k_combinations(set, k) { var i, j, combs, head, tailcombs; if (k > set.length || k <= 0) { return []; } if (k == set.length) { return [set]; } if (k == 1) { combs = []; for (i = 0; i < set.length; i++) { combs.push([set[i]]); } return combs; } // Assert {1 < k < set.length} combs = []; for (i = 0; i < set.length - k + 1; i++) { head = set.slice(i, i+1); tailcombs = k_combinations(set.slice(i + 1), k - 1); for (j = 0; j < tailcombs.length; j++) { combs.push(head.concat(tailcombs[j])); } } return combs; } 

Answer 15

DFS从开始节点s，跟踪遍历期间的DFSpath，并loggingpath，如果你find从path中的节点v到s的边缘。 （v，s）是DFS树中的后端，因此表示包含s的周期。

Answer 16

关于你对排列周期的问题 ，请阅读更多： https ： //www.codechef.com/problems/PCYCLE

你可以试试这个代码（input大小和数字）：

 # include<cstdio> using namespace std; int main() { int n; scanf("%d",&n); int num[1000]; int visited[1000]={0}; int vindex[2000]; for(int i=1;i<=n;i++) scanf("%d",&num[i]); int t_visited=0; int cycles=0; int start=0, index; while(t_visited < n) { for(int i=1;i<=n;i++) { if(visited[i]==0) { vindex[start]=i; visited[i]=1; t_visited++; index=start; break; } } while(true) { index++; vindex[index]=num[vindex[index-1]]; if(vindex[index]==vindex[start]) break; visited[vindex[index]]=1; t_visited++; } vindex[++index]=0; start=index+1; cycles++; } printf("%d\n",cycles,vindex[0]); for(int i=0;i<(n+2*cycles);i++) { if(vindex[i]==0) printf("\n"); else printf("%d ",vindex[i]); } } 

Answer 17

具有后沿的基于DFS的变体确实会find循环，但在许多情况下，它不会是最小的循环。 一般来说，DFS给你的标志是有一个周期，但它不够好，实际上find周期。 例如，想象共享两个边的5个不同的周期。 使用DFS（包括回溯变体）没有简单的方法来识别周期。

约翰逊的algorithm确实给出了所有独特的简单循环，并具有良好的时间和空间复杂性。

但是如果你只想findMINIMAL循环（意思是可能有多个循环经过任何顶点，而我们有兴趣寻找最小的循环）并且你的graphics不是很大，你可以尝试使用下面的简单方法。 这是非常简单，但比约翰逊相当缓慢。

因此，findMINIMAL循环最简单的方法之一就是使用Floydalgorithm来find使用邻接matrix的所有顶点之间的最小path。 这个algorithm远不如约翰逊那样理想，但它非常简单，内部循环非常紧密，对于较小的图（<= 50-100个节点），使用它是绝对有意义的。 时间复杂度是O（n ^ 3），空间复杂度O（n ^ 2），如果你使用父母跟踪和O（1），如果你不这样做。 首先让我们find问题的答案，如果有一个循环。 该algorithm是非常简单的。 以下是Scala中的片段。

  val NO_EDGE = Integer.MAX_VALUE / 2 def shortestPath(weights: Array[Array[Int]]) = { for (k <- weights.indices; i <- weights.indices; j <- weights.indices) { val throughK = weights(i)(k) + weights(k)(j) if (throughK < weights(i)(j)) { weights(i)(j) = throughK } } } 

最初，该algorithm在加权边缘图上运行，以find所有节点对之间的所有最短path（因此为权重参数）。 为使其正常工作，您需要在节点之间存在有向边的情况​​下提供1，否则请提供NO_EDGE。 algorithm执行后，您可以检查主对angular线，如果有值小于NO_EDGE，则该节点参与长度等于该值的循环。 同一周期的每个其他节点将具有相同的值（在主对angular线上）。

为了重build周期本身，我们需要使用稍微修改后的版本的algorithm与父母跟踪。

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = { for (k <- weights.indices; i <- weights.indices; j <- weights.indices) { val throughK = weights(i)(k) + weights(k)(j) if (throughK < weights(i)(j)) { parents(i)(j) = k weights(i)(j) = throughK } } } 

如果在顶点之间存在边缘，则父代matrix最初应包含边缘单元格中的源顶点索引，否则应包含-1。 在函数返回之后，对于每条边，您将引用最短path树中的父节点。 然后很容易恢复实际的周期。

总而言之，我们有以下程序来查找所有最小的周期

  val NO_EDGE = Integer.MAX_VALUE / 2; def shortestPathWithParentTracking( weights: Array[Array[Int]], parents: Array[Array[Int]]) = { for (k <- weights.indices; i <- weights.indices; j <- weights.indices) { val throughK = weights(i)(k) + weights(k)(j) if (throughK < weights(i)(j)) { parents(i)(j) = parents(i)(k) weights(i)(j) = throughK } } } def recoverCycles( cycleNodes: Seq[Int], parents: Array[Array[Int]]): Set[Seq[Int]] = { val res = new mutable.HashSet[Seq[Int]]() for (node <- cycleNodes) { var cycle = new mutable.ArrayBuffer[Int]() cycle += node var other = parents(node)(node) do { cycle += other other = parents(other)(node) } while(other != node) res += cycle.sorted } res.toSet } 

和一个小的主要方法来testing结果

  def main(args: Array[String]): Unit = { val n = 3 val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE)) val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1)) shortestPathWithParentTracking(weights, parents) val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE) val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents) println("The following minimal cycle found:") cycles.foreach(c => println(c.mkString)) println(s"Total: ${cycles.size} cycle found") } 

和输出是

 The following minimal cycle found: 012 Total: 1 cycle found