我知道这个问题有很多答案。但是，我发现他们都没有真正做到这一点。
有人争辩说，循环（几乎）与强连接组件相同（s.在有向图中查找所有循环），因此可以使用为该目标设计的算法。
一些人认为，可以通过 DFS 并检查后边来找到循环（s. boost graph documentation on file dependencies）。
我现在想对是否可以通过 DFS 检测到图中的所有循环并检查后边提出一些建议？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf（在 SO 上找到）说明了一种基于循环基础的方法。就我个人而言，我觉得它不是很直观，所以我正在寻找不同的解决方案。
编辑：我最初的看法显然是错误的。S.下一个答案是“白痴”。
初步意见：我的意见是，当 DFS-VISIT（S. DFS 的伪代码）新进入每个尚未访问的节点时，它确实可以这样工作。从这个意义上说，每个顶点都展示了一个循环的潜在开始。此外，由于 DFS 访问每条边一次，因此也覆盖了通向循环起点的每条边。因此，通过使用 DFS 和后端检查，确实应该可以检测到所有图中的循环。请注意，如果存在具有不同数量的参与者节点的循环（例如三角形、矩形等），则必须进行额外的工作来区分每个循环的实际“形状”。
问问题
14836 次
4 回答
6
我已经彻底回答了这个问题，所以检查一下：
答案的相关部分：
在您的图表上执行深度优先搜索。
您对识别后边感兴趣，即在遍历中，一条边指向被访问节点的祖先（在 DFS 树中，由访问节点的边首次诱导）。例如，如果 DFS 堆栈有节点 [A->B->C->D]，而当您探索 D 时，您会发现一条边 D->B，这就是后边。每个后沿定义一个循环。
更重要的是，由后边引起的循环是图的一组基本循环。“一组基本循环”：您可以通过基本组的 UNIONing 和 XORing 循环来构造图形的所有循环。例如，考虑循环 [A1->A2->A3->A1] 和 [A2->B1->B2->B3->A2]。您可以将它们联合到循环中：[A1->A2->B1->B2->B3->A2->A3->A1]。
于 2010-05-21T13:50:05.740 回答
2
也许这可以以某种方式帮助你，我发现这个网站描述了有向图的彩色 dfs。因此，您可以考虑将 dfs 转换为我在此处介绍的 php。
我添加的是创建森林的部分和查找所有循环的另一部分。因此，请考虑将我的代码的这两部分确定为正确是不安全的。
具有图论知识的人可能可以肯定地进行测试。dfs 部分没有评论，因为它已在参考站点中描述。我建议你以不止一棵树为例，在纸上画出森林（需要 4 种颜色）以便更好地理解。
这是代码：
<?php
//define the graph
$g = Array(
1 => Array(1,2,3,4,5),
2 => Array(1,2,3,4,5),
3 => Array(1,2,3,4,5),
4 => Array(1,2,3,4,5),
5 => Array(1,2,3,4,5)
);
//add needed attributes on the graph
$G = Array();
foreach($g as $name => $children)
{
$child = Array();
foreach($children as $child_name)//attaching a v letter is not needed, just a preference
$child['v'.$child_name] = null;
$G['v'.$name] =
Array('child'=>$child,
'color'=>'WHITE',//is used in dfs to make visit
'discover_time'=>null,//is used in dfs to classify edges
'finish_time'=>null,//is used in dfs to classify edges
'father'=>null,//is used to walk backward to the start of a cycle
'back_edge'=>null//can be omited, this information can be found with in_array(info, child_array)
);
}
new test($G);
class test
{
private $G = Array();//graph
private $C = Array();//cycles
private $F = Array();//forest
private $L = Array();//loops
private $time_counter = 0;
public function __construct($G)
{
$this->G = $G;
foreach($this->G as $node_name => $foo)
{
if($this->G[$node_name]['color'] === 'WHITE')
$this->DFS_Visit($node_name);
}
$tree =array();
foreach($this->G as $node_name => $data)
{
if($data['father'] === null)//new tree found
{
$this->F[] = $tree;//at first an empty array is inserted
$tree = Array();
$tree[$node_name] = $data;
}
else
$tree[$node_name] = $data;
}
array_shift($this->F);//remove the empty array
$this->F[] = $tree;//add the last tree
$this->find_all_elementary_cycles();
file_put_contents('dump.log', count($this->L)." Loops found: \n", FILE_APPEND);
file_put_contents('dump.log', print_r($this->L,true)."\n", FILE_APPEND);
file_put_contents('dump.log', count($this->C)." Cycles found: \n", FILE_APPEND);
file_put_contents('dump.log', print_r($this->C,true)."\n", FILE_APPEND);
file_put_contents('dump.log', count($this->F)." trees found in the Forest: \n", FILE_APPEND);
file_put_contents('dump.log', print_r($this->F,true)."\n", FILE_APPEND);
}
public function find_all_elementary_cycles()
{
/*** For each tree of the forest ***/
foreach($this->F as $tree)
{
/*** Foreach node in the tree ***/
foreach($tree as $node_name => $node)
{
/*** If this tree node connects to some child with backedge
(we hope to avoid some loops with this if) ***/
if ( $node['back_edge'] === true )
/*** Then for every child ***/
foreach ( $node['child'] as $child_name => $edge_classification)
if($edge_classification === 'BACK_EDGE')
$this->back_edge_exploit($node_name, $child_name, $tree);
}
}
}
private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
/*** The input of this function is a back edge, a back edge is defined as follows
-a sender node: which stands lower in the tree and a reciever node which of course stands higher
***/
/*** We want to get rid of loops, so check for a loop ***/
if($back_edge_sender == $back_edge_receiver)
return $this->L[] = $back_edge_sender;//we need to return cause no there is no cycle in a loop
/*** For this backedge sender node the backedge reciever might send a direct edge to the sender ***/
if( isset($this->G[$back_edge_receiver]['child'][$back_edge_sender]) > 0 )
/*** This edge that the reciever sends could be a tree edge, this will happen
-in the case that: the backedge reciever is a father, but it can be a forward edge
-in this case: for the forward edge to exist the backedge reciever does not have to be
-a father onlly: it can also be an ancestore. Whatever of both cases, we have a cycle
***/
if( $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'TREE_EDGE' or
$this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'FORWARD_EDGE')
$this->C[md5(serialize(Array($back_edge_receiver,$back_edge_sender)))]
= Array($back_edge_receiver,$back_edge_sender);
/*** Until now we have covered, loops, cycles of the kind father->child which occur from one tree edge
- and one: back edge combination, and also we have covered cycles of the kind ancestore->descendant
-which: occur from the combination of one forward edge and one backedge (of course might happen that
-a father: can send to the child both forward and tree edge, all these are covered already).
-what are left: are the cycles of the combination of more than one tree edges and one backedge ***/
$cycle = Array();
attach_node://loops must be handled before this, otherwise goto will loop continously
$cycle[] = $back_edge_sender; //enter the backedge sender
$back_edge_sender = $tree[$back_edge_sender]['father']; //backedge sender becomes his father
if($back_edge_sender !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
goto attach_node;//the loop again
$cycle[] = $back_edge_receiver;
$cycle = array_reverse($cycle);
$this->C[md5(serialize($cycle))] = $cycle;
}
private function DFS_Visit($node_name)
{
$this->G[$node_name]['color'] = 'GRAY';
$this->G[$node_name]['discover_time'] = $this->time_counter++;
foreach($this->G[$node_name]['child'] as $child_name => $foo)
{
if($this->G[$child_name]['color'] === 'BLACK') {#child black
if( $this->G[$node_name]['discover_time'] <
$this->G[$child_name]['discover_time'] ){#time of father smaller
$this->G[$node_name]['child'][$child_name] = 'FORWARD_EDGE';
}
else{#time of child smaller
$this->G[$node_name]['child'][$child_name] = 'CROSS_EDGE';
}
}
elseif($this->G[$child_name]['color'] === 'WHITE'){#child white
$this->G[$node_name]['child'][$child_name] = 'TREE_EDGE';
$this->G[$child_name]['father'] = $node_name;#father in the tree
$this->DFS_Visit($child_name);
}#child discovered but not explored (and father discovered)
elseif($this->G[$child_name]['color'] === 'GRAY'){#child gray
$this->G[$node_name]['child'][$child_name] = 'BACK_EDGE';
$this->G[$node_name]['back_edge'] = true;
}
}//for
$this->G[$node_name]['color'] = 'BLACK';//fully explored
$this->G[$node_name]['finish_time'] = $this->time_counter++;
}
}
?>
这是输出：
5 Loops found: Array (
[0] => v1
[1] => v2
[2] => v3
[3] => v4
[4] => v5 )
16 Cycles found: Array (
[336adbca89b3389a6f9640047d07f24a] => Array
(
[0] => v1
[1] => v2
)
[d68df8cdbc98d846a591937e9dd9cd70] => Array
(
[0] => v1
[1] => v3
)
[cad6b68c862d3a00a35670db31b76b67] => Array
(
[0] => v1
[1] => v2
[2] => v3
)
[1478f02ce1faa31e122a61a88af498e4] => Array
(
[0] => v2
[1] => v3
)
[0fba8cccc8dceda9fe84c3c93c20d057] => Array
(
[0] => v1
[1] => v4
)
[c995c93b92f8fe8003ea77617760a0c9] => Array
(
[0] => v1
[1] => v2
[2] => v3
[3] => v4
)
[8eae017bc12f0990ab42196af0a1f6a8] => Array
(
[0] => v2
[1] => v4
)
[57c0cc445b506ba6d51dc3c2f06fd926] => Array
(
[0] => v2
[1] => v3
[2] => v4
)
[18cef1bbe850dca5d2d7b6bfea795a23] => Array
(
[0] => v3
[1] => v4
)
[e0bd0c51bfa4df20e4ad922f57f6fe0d] => Array
(
[0] => v1
[1] => v5
)
[6a8b7681b160e28dd86f3f8316bfa16e] => Array
(
[0] => v1
[1] => v2
[2] => v3
[3] => v4
[4] => v5
)
[85e95d3e4dc97e066ec89752946ccf0c] => Array
(
[0] => v2
[1] => v5
)
[633c7cf8df43df75a24c104d9de09ece] => Array
(
[0] => v2
[1] => v3
[2] => v4
[3] => v5
)
[769f8ebc0695f46b5cc3cd444be2938a] => Array
(
[0] => v3
[1] => v5
)
[87028339e63fd6c2687dc5488ba0818c] => Array
(
[0] => v3
[1] => v4
[2] => v5
)
[c2b28cdcef48362ceb0d8fb36a142254] => Array
(
[0] => v4
[1] => v5
)
)
1 trees found in the Forest: Array (
[0] => Array
(
[v1] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => TREE_EDGE
[v3] => FORWARD_EDGE
[v4] => FORWARD_EDGE
[v5] => FORWARD_EDGE
)
[color] => BLACK
[discover_time] => 0
[finish_time] => 9
[father] =>
[back_edge] => 1
)
[v2] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => TREE_EDGE
[v4] => FORWARD_EDGE
[v5] => FORWARD_EDGE
)
[color] => BLACK
[discover_time] => 1
[finish_time] => 8
[father] => v1
[back_edge] => 1
)
[v3] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => BACK_EDGE
[v4] => TREE_EDGE
[v5] => FORWARD_EDGE
)
[color] => BLACK
[discover_time] => 2
[finish_time] => 7
[father] => v2
[back_edge] => 1
)
[v4] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => BACK_EDGE
[v4] => BACK_EDGE
[v5] => TREE_EDGE
)
[color] => BLACK
[discover_time] => 3
[finish_time] => 6
[father] => v3
[back_edge] => 1
)
[v5] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => BACK_EDGE
[v4] => BACK_EDGE
[v5] => BACK_EDGE
)
[color] => BLACK
[discover_time] => 4
[finish_time] => 5
[father] => v4
[back_edge] => 1
)
)
)
编辑1：back_edge_exploit该版本可以替换该方法
：
![private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
/*** The input of this function is a back edge, a back edge is defined as follows
-a sender node: which stands lower in the tree and a reciever node which of course stands higher
***/
/*** We want to get rid of loops, so check for a loop ***/
if($back_edge_sender == $back_edge_receiver)
return $this->L\[\] = $back_edge_sender;//we need to return cause no there is no cycle in a loop
$cycle = Array();//There is always a cycle which is a combination of tree edges and on backedge
$edges_count = 0; //If the cycle has more than 2 nodes we need to check for forward edge
$backward_runner = $back_edge_sender;//this walks backward up to the start of cycle
attach_node://loops must be handled before this, otherwise goto will loop continously
$edges_count++;
$cycle\[\] = $backward_runner; //enter the backedge sender
$backward_runner = $tree\[$backward_runner\]\['father'\]; //backedge sender becomes his father
if($backward_runner !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
goto attach_node;//the loop again
else
$cycle\[\] = $backward_runner;
if($edges_count>1 and $this->G\[$back_edge_receiver\]\['child'\]\[$back_edge_sender\] === 'FORWARD_EDGE' )
$this->C\[\] = Array($back_edge_receiver,$back_edge_sender);
$this->C\[\] = array_reverse($cycle); //store the tree edge->back_edge cycle
}][2]
编辑 2：
我不得不说我发现这back_edge_exploit是不够的，它只会找到由树边缘和一个后边缘组成的循环。
****编辑3：****虽然发现这个解决方案不完整，但它有一些有用的信息，即使它本身的不足也是一条信息，所以我认为保留它可能会有用。但我编辑答案的主要原因是我找到了另一个解决方案，我将在下面介绍。
但在此之前，可以就 dfs 方法发出其他通知，通过遍历所有交叉、前向、树、后边缘的任何有效组合可能会发生循环。因此，找到依赖 dfs 信息的实际周期并非易事（需要额外的代码），请考虑以下示例：
只要涉及到新的解决方案，它在 1970 年的一篇旧论文中被描述为 James C. Tiernan（查看此链接）作为在有向图中查找所有基本循环的有效算法。还有一个没有 goto 的现代实现在这里查看
我的基本循环算法（就是这个名字）的实现是在 php 中，并且尽可能接近原始版本。我已经检查过了，它可以工作。它是关于有向图的，如果你声明你的图表有一个有向循环 v1->v2->v3 和另一个有向循环 v2->v3->v1 那么两个循环都会被发现，这是合乎逻辑的，因为它适用于有向图表。
至于无向图，作者建议了其他算法，它们比修改算法提供更好的解决方案，但是可以通过修改图定义并添加对长度为 2 的循环的额外检查来完成，这些循环被视为无向边。特别是三个节点的无向循环将在定义中定义两次，每个方向一次，如下所示：v1->v2->v3 和 v3->v2->v1。然后算法会找到它两次，每个方向一次，然后修改一条线EC3_Circuit_Confirmation可以切割额外的一条。
节点是按顺序定义的，可以更改常量first和邻接表以使第一个节点从零开始计数。
这是 Tiernan 的 EC 算法的 php 代码：
<?php
define(first,1); //Define how to start counting, from 0 or 1
//nodes are considered to be sequential
$G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1);
$N=key(array_slice($G, -1, 1, TRUE));//last key of g
$H=Array(Array());
$P = Array();
$P[first] = first;
$k = first;
$C = Array();//cycles
$L = Array();//loops
########################## ALGORITHM START #############################
#[Path Extension]
EC2_Path_Extension:
//scan adjacency list
foreach($G[$P[$k]] as $j => $adj_node)
//if there is an adjacent node bigger than P[1] and this nodes does not belong in P
if( ($adj_node > $P[first]) and (in_array($adj_node, $P))===false and
(count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false)
{
$k++;
$P[$k] = $G[$P[$k-1]][$j];
goto EC2_Path_Extension;
}
#[EC3 Circuit Confirmation]
EC3_Circuit_Confirmation:
if(!in_array($P[first], $G[$P[$k]]))
goto EC4_Vertex_Closure;
//otherwise
if (count($P)===1)
$L[] = current($P);
else
$C[] = implode($P);
#[EC4 Vertex Closure]
EC4_Vertex_Closure:
if($k===first)
goto EC5_Advance_Initial_Vertex;
$H[$P[$k]] = Array();
$H[$P[$k-1]][] = $P[$k];
unset($P[$k]);
$k--;
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[first] === $N)
goto EC6_Terminate;
$P[first]++;
$k=first;
//Reset H
$H=Array(Array());
goto EC2_Path_Extension;
EC6_Terminate:
########################### ALGORITHM END ##################################
echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n";
echo count($C)." cycles found!\n".implode("\n",$C)."\n";
/*** Original graph found in the paper ***/
//$G[first] = Array(2); $G[] = Array(2,3,4);
//$G[] = Array(5); $G[] = Array(3); $G[] = Array(1);
?>
于 2012-03-12T10:30:31.310 回答
1
My suggestion is to use Tarjan's algorithm to find set of strongly connected components, and Hierholzer's algorithm to find all cycles in the strongly connected component.
Here is the link for the Java implementation with a test case: http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html
于 2013-12-02T05:48:13.127 回答
0
如果遍历算法只访问每条边一次，则它无法找到所有循环。一条边可能是多个循环的一部分。
顺便说一句，什么是后端？
另外，也许您应该改写/格式化您的问题。很难阅读。
于 2010-05-17T06:43:54.910 回答