如何从/到给定节点的有向图中找到（迭代）所有循环？
例如，我想要这样的东西：
A->B->A
A->B->C->A
但不是：B->C->B
问问题
255865 次
17 回答
123
我在搜索中找到了这个页面，由于循环与强连接组件不同，我继续搜索，最后，我找到了一个有效的算法，它列出了有向图的所有（基本）循环。它来自 Donald B. Johnson，该论文可在以下链接中找到：
http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
可以在以下位置找到 java 实现：
http://normalisiert.de/code/java/elementaryCycles.zip
可以在这里找到约翰逊算法的Mathematica演示，可以从右侧下载实现（“下载作者代码”）。
注意：实际上，有很多算法可以解决这个问题。其中一些列在本文中：
http://dx.doi.org/10.1137/0205007
根据文章，约翰逊的算法是最快的。
于 2010-05-08T15:51:29.547 回答
40
带有回溯的深度优先搜索应该在这里工作。保留一个布尔值数组以跟踪您之前是否访问过某个节点。如果你用完了新的节点（没有碰到你已经去过的节点），那么只需回溯并尝试不同的分支。
如果你有一个邻接表来表示图形，那么 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)
于 2009-02-14T16:20:16.827 回答
26
首先 - 你真的不想尝试从字面上找到所有的周期，因为如果有 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 。
于 2013-08-15T17:33:50.300 回答
25
我发现解决这个问题的最简单的选择是使用名为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']]
于 2015-11-27T11:59:34.743 回答
6
基于 DFS 的带有后边缘的变体确实会找到循环，但在许多情况下它不会是最小循环。一般来说，DFS 会给你一个标志，表明存在一个循环，但它还不足以真正找到循环。例如，想象 5 个不同的循环共享两条边。仅使用 DFS（包括回溯变体）没有简单的方法来识别循环。
Johnson 算法确实给出了所有唯一的简单循环，并且具有良好的时间和空间复杂度。
但是，如果您只想找到 MINIMAL 循环（意味着可能有不止一个循环通过任何顶点，我们有兴趣找到最小循环）并且您的图形不是很大，您可以尝试使用下面的简单方法。与约翰逊的相比，它非常简单但相当慢。
因此，找到MINIMAL循环的最简单方法之一是使用 Floyd 算法使用邻接矩阵找到所有顶点之间的最小路径。这个算法远没有 Johnson 算法那么最优，但它非常简单，而且它的内部循环非常紧凑，以至于对于较小的图（<=50-100 个节点），使用它绝对是有意义的。如果使用父跟踪，时间复杂度为 O(n^3)，空间复杂度为 O(n^2)，如果不使用，则为 O(1)。首先让我们找到问题的答案是否存在循环。该算法非常简单。下面是 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
}
}
}
最初，该算法在加权边图上运行以查找所有节点对之间的所有最短路径（因此使用权重参数）。要使其正常工作，如果节点之间存在有向边，则需要提供 1，否则需要提供 NO_EDGE。算法执行后，可以检查主对角线，如果有小于 NO_EDGE 的值，则该节点参与长度等于该值的循环。同一循环的每个其他节点都将具有相同的值（在主对角线上）。
为了重建循环本身，我们需要使用稍微修改过的带有父跟踪的算法版本。
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
}
}
}
如果顶点之间存在边，则父矩阵最初应在边单元中包含源顶点索引，否则应包含-1。函数返回后，对于每条边，您都将引用最短路径树中的父节点。然后很容易恢复实际周期。
总而言之，我们有以下程序来查找所有最小周期
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
}
和一个小的主要方法只是为了测试结果
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
于 2016-09-15T21:36:21.553 回答
5
澄清：
强连通组件将找到其中至少有一个循环的所有子图，而不是图中所有可能的循环。例如，如果您采用所有强连接组件并将它们中的每一个折叠/分组/合并到一个节点（即每个组件一个节点），您将得到一棵没有循环的树（实际上是一个 DAG）。每个组件（基本上是一个包含至少一个循环的子图）内部可以包含更多可能的循环，因此 SCC 不会找到所有可能的循环，它会找到所有可能的组，至少有一个循环，如果你分组他们，那么图形将没有循环。
正如其他人所提到的，要在图中找到所有简单的循环，约翰逊的算法是一个候选者。
于 2015-05-31T03:40:35.817 回答
4
我曾经收到过这个作为面试问题的问题，我怀疑这发生在你身上，你来这里寻求帮助。将问题分解为三个问题，它会变得更容易。
- 你如何确定下一条有效路线
- 你如何确定一个点是否已被使用
- 你如何避免再次跨越同一点
问题 1) 使用迭代器模式提供一种迭代路由结果的方法。放置逻辑以获取下一条路线的好地方可能是迭代器的“moveNext”。要找到有效的路线，这取决于您的数据结构。对我来说，这是一个充满有效路线可能性的 sql 表，所以我必须构建一个查询来获取给定源的有效目的地。
问题2）当你找到它们时将每个节点推入一个集合中，这意味着你可以通过询问你正在构建的集合很容易地查看你是否在一个点上“加倍”。
问题 3）如果在任何时候你看到你正在加倍回来，你可以从集合中弹出东西并“备份”。然后从那时起再次尝试“前进”。
技巧：如果您使用的是 Sql Server 2008，则可以使用一些新的“层次结构”来快速解决这个问题，如果您将数据构建在树中。
于 2009-02-13T19:18:51.477 回答
3
在无向图的情况下，最近发表的一篇论文（无向图中循环和 st 路径的优化列表）提供了一个渐近最优解。你可以在这里阅读它http://arxiv.org/abs/1205.2766或在这里http://dl.acm.org/citation.cfm?id=2627951 我知道它不能回答你的问题，但因为标题你的问题没有提到方向，它可能对谷歌搜索仍然有用
于 2014-12-02T15:35:41.923 回答
1
从节点 X 开始并检查所有子节点（如果无向，父节点和子节点是等效的）。将这些子节点标记为 X 的子节点。从任何这样的子节点 A 中，将其标记为 A 的子节点 X'，其中 X' 被标记为距离 2 步。）。如果您稍后点击 X 并将其标记为 X'' 的子级，则表示 X 处于 3 节点循环中。回溯到它的父级很容易（因为算法不支持这一点，所以你会找到任何一个有 X' 的父级）。
注意：如果图是无向的或具有任何双向边，则此算法会变得更加复杂，假设您不想在一个循环中遍历同一条边两次。
于 2009-02-13T16:47:42.310 回答
1
如果您想要在图中找到所有基本电路，您可以使用 JAMES C. TIERNAN 的 EC 算法，该算法自 1970 年以来在一篇论文中发现。
我设法在 php 中实现的非常原始的EC 算法（希望没有错误如下所示）。如果有的话，它也可以找到循环。此实现中的电路（试图克隆原始电路）是非零元素。这里的零代表不存在（我们知道它是空的）。
除了下面的其他实现，它使算法更加独立，这意味着节点可以从任何地方开始，甚至可以从负数开始，例如 -4、-3、-2、.. 等。
在这两种情况下，都要求节点是连续的。
您可能需要研究原始论文James C. Tiernan Elementary Circuit 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);
?>
那么这是另一个实现，更独立于图形，没有 goto 和没有数组值，而是使用数组键，路径，图形和电路存储为数组键（如果你喜欢使用数组值，只需更改所需的行）。示例图从 -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
?>
我已经分析并记录了 EC，但不幸的是，文档是希腊文的。
于 2013-03-21T12:47:29.470 回答
1
查找 DAG 中的所有循环涉及两个步骤（算法）。
第一步是使用 Tarjan 算法找到强连通分量的集合。
- 从任意顶点开始。
- 来自该顶点的 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] 的所有节点都在同一个强连通分量中。
第二步是在连接的组件中找到循环（路径）。我的建议是使用 Hierholzer 算法的修改版本。
这个想法是：
- 选择任何起始顶点 v，然后沿着从该顶点开始的边轨迹，直到返回 v。不可能卡在 v 以外的任何顶点，因为所有顶点的度数相等，确保当轨迹进入另一个顶点时顶点 w 必须有一条未使用的边离开 w。这样形成的游览是一个封闭的游览，但可能不会覆盖初始图的所有顶点和边。
- 只要存在属于当前游览但相邻边不属于游览的顶点 v，则从 v 开始另一条路径，沿着未使用的边直到您返回 v，并将以这种方式形成的游览加入到以前的巡回演出。
以下是带有测试用例的 Java 实现的链接：
http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html
于 2013-12-02T05:37:03.460 回答
0
我偶然发现了以下算法，它似乎比约翰逊的算法更有效（至少对于较大的图表）。但是，与 Tarjan 的算法相比，我不确定它的性能。
此外，到目前为止，我只检查了三角形。如果有兴趣，请参阅 Norishige Chiba 和 Takao Nishizeki 的“Arboricity and Subgraph Listing Algorithms”（http://dx.doi.org/10.1137/0214017）
于 2010-05-17T13:57:11.547 回答
0
从起始节点 s 开始 DFS，在遍历过程中跟踪 DFS 路径，如果在到 s 的路径中找到节点 v 的边，则记录该路径。(v,s) 是 DFS 树中的后沿，因此表示包含 s 的循环。
于 2015-05-29T06:00:40.833 回答
0
二楼答案中伪代码的 DFS c++ 版本：
void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
if(visited[v]) {
if(v == start) {
for(auto c : path)
cout << c << " ";
cout << endl;
return;
}
else
return;
}
visited[v] = true;
path.push_back(v);
for(auto i : G[v])
findCircleUnit(start, i, visited, path);
visited[v] = false;
path.pop_back();
}
于 2020-04-04T13:11:40.290 回答
0
关于您关于Permutation Cycle的问题，请在此处阅读更多信息： https ://www.codechef.com/problems/PCYCLE
你可以试试这个代码（输入大小和位数）：
# 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]);
}
}
于 2015-08-02T23:33:51.017 回答
-1
于 2009-02-15T17:33:18.583 回答