私はこの質問にかなりの数の答えが存在することを知っています。しかし、私はそれらのどれも実際にそれを要点に持って来ていないのを見つけました。
サイクルは（ほぼ）強連結成分と同じであると主張する人もいます（有向グラフですべてのサイクルを見つける）。そのため、その目標のために設計されたアルゴリズムを使用できます。サイクルの検索は
DFSを介して実行でき、バックエッジをチェックできる
と主張する人もいます（ファイルの依存関係に関するグラフのドキュメントを強化します）。グラフ内のすべてのサイクルをDFSを介して検出し、バックエッジをチェックできる
かどうかについて、いくつかの提案がありますか？http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf
（ここでSOにあります）は、サイクルベースに基づく1つの方法を述べています。私個人的には、あまり直感的ではないので、別の解決策を探しています。
編集：私の最初の意見は明らかに間違っていました。S.「モロン」による次の答え。
最初の意見：私の意見では、DFS-VISIT（DFSの擬似コード）がまだアクセスされていない各ノードに新たに入るので、実際にそのように機能する可能性があります。その意味で、各頂点は潜在的なサイクルの開始を示します。さらに、DFSが各エッジに1回アクセスすると、サイクルの開始点につながる各エッジもカバーされます。したがって、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 への変換を修正することを検討できます。
私が追加したのは、森を作成する部分と、すべてのサイクルを見つけるための別の部分です。したがって、私のコードのこれらの 2 つの部分を正しいと見なすのは安全ではないことを考慮してください。
グラフ理論の知識がある人は、確実にテストできるかもしれません。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ツリーのエッジと 1 つのバック エッジで作成されたサイクルのみを見つけるには不十分であること
がわかったと言わざるを得ません。
**** 編集 3: **** この解決策は不完全であることが判明しましたが、いくつかの有用な情報があり、それ自体が不十分であっても情報の一部であるため、保持しておくと役立つ場合があると思います。しかし、私が回答を編集した主な理由は、以下に示す別の解決策を見つけたからです。
しかし、その前に、dfs アプローチについて別の通知を行うことができます。クロス、フォワード、ツリー、バック エッジのすべての有効な組み合わせを歩くことによって発生する可能性のあるサイクルがあります。したがって、dfs 情報に依存する実際のサイクルを見つけることは簡単ではありません (追加のコードが必要です)。次の例を検討してください。
新しいソリューションに関する限り、James C. Tiernan による 1970 年の古い論文 (このリンクを確認してください) で、有向グラフ内のすべての基本サイクルを見つけるための効率的なアルゴリズムとして説明されています。また、goto を使用しない最新の実装もあります。こちらを参照してください。
Elementary Cycle Algorithm (それが名前です) の私の実装は php にあり、可能な限りオリジナルに近いものです。私はすでにそれをチェックしており、動作します。有向グラフについてです。有向サイクル v1->v2->v3 と別の有向サイクル v2->v3->v1 があるようにグラフを宣言すると、有向グラフで動作するため、両方のサイクルが論理的に検出されます。グラフ。
無向グラフに関しては、著者はアルゴリズムを変更するよりも優れた解決策となる他のアルゴリズムを提案していますが、グラフ定義を変更し、無向エッジと見なされる長さ 2 のサイクルの追加チェックを追加することで解決できます。特に、3 つのノードの無向サイクルは、定義で 2 回 (方向ごとに 1 回) 定義されます。たとえば、v1->v2->v3 と v3->v2->v1 のようになります。次に、アルゴリズムはそれを方向ごとに 1 回、2 回検出します。次に、1 行を変更するとEC3_Circuit_Confirmation、余分な行が切り取られます。
ノードは順番に定義されます。定数firstと隣接リストを変更して、最初のノードを 0 または 1 から数えることができます。
これは、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 に答える
0
トラバーサル アルゴリズムが各エッジを 1 回だけ訪問する場合、すべてのサイクルを見つけることはできません。エッジは、複数のサイクルの一部である可能性があります。
ところで、バックエッジとは何ですか？
また、おそらく質問を言い換え/フォーマットする必要があります。とても読みにくいです。
于 2010-05-17T06:43:54.910 に答える