在有向图中查找所有的周期
我如何find(迭代)有向图中所有的周期从/到给定的节点?
例如,我想要这样的东西:
A->B->A A->B->C->A
但不是:B-> C-> B
我在我的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是最快的。
深度首先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)
首先 – 你不是真的想试图从字面上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 。
我发现解决这个问题最简单的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']]
澄清:
-
强连通组件将查找至less有一个周期的所有子图,而不是图中所有可能的周期。 例如,如果将所有强连通的组件合并,并将它们中的每一个合并到一个节点(即每个组件的节点),则会得到一个没有周期的树(实际上是一个DAG)。 每个组件(基本上是一个至less有一个周期的子图)在内部可以包含更多的可能的周期,所以SCC将不会find所有可能的周期,它将find所有可能的组,至less有一个周期,如果组他们,那么图表将不会有周期。
-
像其他人提到的那样,在图中find所有简单的循环,约翰逊的algorithm是一个候选人。
我曾经作为一个面试问题给过这个问题,我怀疑这件事发生在你身上,你是来这里寻求帮助的。 把问题分解成三个问题就变得简单了。
- 你如何确定下一个有效的路线
- 你如何确定一个点是否已被使用
- 你怎么避免再次跨越同一点
问题1)使用迭代器模式提供迭代路由结果的方法。 把逻辑放到下一个路线的好地方可能就是迭代器的“moveNext”了。 要find一个有效的路线,这取决于你的数据结构。 对我来说,这是一个充满了有效的路线可能性的SQL表,所以我不得不build立一个查询来获得给定的源有效的目的地。
问题2)当你find它们的时候,将每个节点推到一个集合中,这意味着通过询问你正在build立的集合,你可以很容易地看到你是否“倍增”了一个点。
问题3)如果在任何时候你看到你正在翻倍,你可以从集合中popup东西并“备份”。 然后从那一点开始尝试再次“前进”。
Hack:如果您使用的是Sql Server 2008,那么您可以使用一些新的“层次结构”来快速解决这个问题,如果您在树中构build数据。
从节点X开始,检查所有的子节点(父节点和子节点是否相同,如果是无向的)。 将这些子节点标记为X的子节点。从任何这样的子节点A,将它标记为A,X'的子节点,其中X'标记为2步。 如果以后按X并将其标记为X的子项,则表示X处于3节点循环中。 回溯到它的父母很容易(因为,algorithm不支持这个,所以你会发现任何父母有X')。
注意:如果graphics是无向的或者有任何双向的边缘,这个algorithm变得更加复杂,假设你不想在一个周期内两次遍历相同的边缘。
在DAG中查找所有周期涉及两个步骤(algorithm)。
第一步是使用Tarjan的algorithm来find一组强连通的组件。
- 从任意的顶点开始。
- 来自该顶点的DFS。 对于每个节点x,保留两个数字,dfs_index [x]和dfs_lowval [x]。 dfs_index [x]在该节点被访问时存储,而dfs_lowval [x] = min(dfs_low [k]),其中k是x的所有孩子,而不是dfs生成树中x的直接父亲。
- 所有具有相同dfs_lowval [x]的节点都位于相同的强连接组件中。
第二步是在连接的组件中查找循环(path)。 我的build议是使用Hierholzeralgorithm的修改版本。
这个想法是:
- select任何起始顶点v,然后沿着从该顶点开始的一条边,直到返回到v。由于所有顶点的偶数度确保当轨迹进入另一个顶点时,不可能卡住v以外的任何顶点顶点w必须有一个未使用的边离开w。 以这种方式形成的巡视是闭合的巡视,但是可能不包括初始graphics的所有顶点和边缘。
- 只要存在一个属于当前巡视的顶点v,但是它的相邻边不属于巡视的一部分,则从v开始另一个巡视,沿着未使用的边,直到返回到v,并将以这种方式形成的巡视join到以前的旅游。
下面是一个带有testing用例的Java实现的链接:
http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html
在无向图的情况下,最近发表的论文( 无向图中的循环和stpath的最优列表 )提供了渐近最优解。 你可以在这里阅读它http://arxiv.org/abs/1205.2766或在这里http://dl.acm.org/citation.cfm?id=2627951我知道它不回答你的问题,但自你的问题没有提到方向,它可能仍然是有用的谷歌search
如果你想要在图中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了欧共体,但不幸的是文件是用希腊文写成的。
我偶然发现了一个似乎比Johnsonalgorithm更有效的algorithm(至less对于更大的图)。 然而,我不确定它的性能与Tarjan的algorithm相比。
另外,到目前为止我只检查了三angular形。 如果感兴趣的话,请参阅千叶千叶和西尾高雄( http://dx.doi.org/10.1137/0214017 )的“Arboricity和Subgraph Listing Algorithms”
你不能做一个小的recursion函数来遍历节点吗?
readDiGraph( string pathSoFar, Node x) { if(NoChildren) MasterList.add( pathsofar + Node.name ) ; foreach( child ) { readDiGraph( pathsofar + "->" + this.name, child) } }
如果你有大量的节点,你将用完堆栈
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; }
DFS从开始节点s,跟踪遍历期间的DFSpath,并loggingpath,如果你find从path中的节点v到s的边缘。 (v,s)是DFS树中的后端,因此表示包含s的周期。
关于你对排列周期的问题 ,请阅读更多: 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]); } }
具有后沿的基于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