-
26 votesanswersviews
如何检测有向图是否是循环的?
我们如何检测有向图是否是循环的?我认为使用广度优先搜索,但我不确定 . 有任何想法吗? -
3 votesanswersviews
使用递归回溯在有向图中查找所有周期
我正在使用递归回溯来查找有向图中的循环 . 这个here有一个建议的伪代码,它在这里: dfs(adj,node,visited): if (visited[node]): if (node == start): "found a path" return; visited[node]=YES; for child... -
0 votesanswersviews
从循环图中提取树/ DAG
给定有向循环图,如何获得代表输入图的各种DAG /树?实际上,我想从给定的电路(定向和循环)图中提取各种树 . 任何帮助将不胜感激 . -
1 votesanswersviews
使用Perl在有向图中查找所有循环依赖项
I am looking for the solution to a problem where Perl script could detect all the cyclic nodes in a directed graph? 例如,我有以下图表: A<-N<-G<-L<- A<-B<-C<-D<-E<-F<-A Be a Graph... -
2 votesanswersviews
将循环转换为非循环图
我想将循环图转换为非循环图 . 是否有伪代码可以做到这一点?我确实尝试过搜索,但大部分都是基于马尔可夫链或研究文章返回的数学 . 我想写一个程序来做它,任何方向都会有用 . 例如,请考虑下面的图表 . A->B B->C C->A 我在一个讲座中看到了一个解决方案,但是讲座中提到了一些解决方案,并参考了之前教过的内容并且无法理解 . 简而言之,它以一种方式复制层中的节点,结束图... -
2 votesanswersviews
在有向图中使用DFS进行循环检测绝对需要回溯吗?
我遇到了这个SO post,其中建议在有向图中使用DFS进行循环检测由于回溯而更快 . 在这里,我引用该链接: 深度优先搜索比广度优先搜索更有效,因为您可以更快地回溯 . 如果使用调用堆栈,它也更容易实现,但这依赖于不会溢出堆栈的最长路径 . 此外,如果您的图表是定向的,那么您不仅要记住您是否访问过某个节点,还要记得您是如何到达那里的 . 否则你可能会认为你已经找到了一个循环,但实际上你所拥有的...