特定のノードから/への有向グラフのすべてのサイクルを見つける (反復する) にはどうすればよいですか?
たとえば、次のようなものが必要です。
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
Johnson のアルゴリズムのMathematicaのデモはここにあります。実装は右からダウンロードできます ( 「著者コードのダウンロード」 )。
注: 実際には、この問題には多くのアルゴリズムがあります。それらのいくつかは、この記事にリストされています。
http://dx.doi.org/10.1137/0205007
記事によると、Johnson のアルゴリズムが最も高速です。
于 2010-05-08T15:51:29.547 に答える
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 はサイクルがあることを示すフラグを提供しますが、実際にサイクルを見つけるには十分ではありません。たとえば、2 つのエッジを共有する 5 つの異なるサイクルを想像してください。DFS (バックトラッキング バリアントを含む) だけを使用してサイクルを特定する簡単な方法はありません。
ジョンソンのアルゴリズムは確かに、すべての一意の単純なサイクルを提供し、時間と空間の複雑さが優れています。
しかし、MINIMAL サイクルだけを見つけたい場合 (つまり、任意の頂点を通過するサイクルが 1 つ以上ある可能性があり、最小のものを見つけることに関心がある)、グラフがそれほど大きくない場合は、以下の簡単な方法を使用してみることができます。非常にシンプルですが、ジョンソンのものに比べてかなり遅いです。
したがって、MINIMALサイクルを見つける最も簡単な方法の 1 つは、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
}
}
}
本来、このアルゴリズムは加重エッジ グラフで動作し、ノードのすべてのペア間のすべての最短パスを見つけます (したがって、 weights 引数)。正しく機能させるには、ノード間に有向エッジがある場合は 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
明確にするために：
強連結成分は、グラフ内のすべての可能なサイクルではなく、少なくとも 1 つのサイクルを含むすべてのサブグラフを検索します。たとえば、すべての強く接続されたコンポーネントを取り、それらのそれぞれを 1 つのノード (つまり、コンポーネントごとのノード) に折りたたむ/グループ化する/マージすると、サイクルのないツリー (実際には DAG) が得られます。各コンポーネント (基本的には少なくとも 1 つのサイクルを含むサブグラフ) は、内部的にさらに多くの可能なサイクルを含むことができるため、SCC は可能なすべてのサイクルを見つけるわけではなく、少なくとも 1 つのサイクルを持つすべての可能なグループを見つけます。それらの場合、グラフにはサイクルがありません。
他の人が述べたように、グラフ内のすべての単純なサイクルを見つけるには、ジョンソンのアルゴリズムが候補です。
于 2015-05-31T03:40:35.817 に答える
4
私は一度インタビューの質問としてこれを与えられました、私はこれがあなたに起こったのではないかと思います、そしてあなたは助けのためにここに来ています。問題を3つの質問に分ければ、簡単になります。
- 次の有効なルートをどのように決定しますか
- ポイントが使用されたかどうかをどのように判断しますか
- 同じポイントを再び越えることをどのように回避しますか
問題1）イテレータパターンを使用して、ルート結果を反復する方法を提供します。次のルートを取得するためのロジックを配置するのに適した場所は、おそらくイテレータの「moveNext」です。有効なルートを見つけるには、データ構造によって異なります。私にとって、それは有効なルートの可能性でいっぱいのSQLテーブルだったので、ソースを指定して有効な宛先を取得するためのクエリを作成する必要がありました。
問題2）各ノードを見つけたら、それらを取得したらコレクションにプッシュします。これは、作成しているコレクションにその場で問い合わせることで、ポイントを「倍増」しているかどうかを簡単に確認できることを意味します。
問題3）いつでも倍増していることがわかった場合は、コレクションから物を取り出して「バックアップ」することができます。次に、その時点からもう一度「前進」してみてください。
ハック：SQL Server 2008を使用している場合、データをツリーで構造化すると、これをすばやく解決するために使用できる新しい「階層」がいくつかあります。
于 2009-02-13T19:18:51.477 に答える
3
無向グラフの場合、最近公開された論文 (無向グラフのサイクルと st-path の最適なリスト) は、漸近的に最適なソリューションを提供します。ここで読むことができますhttp://arxiv.org/abs/1205.2766またはここhttp://dl.acm.org/citation.cfm?id=2627951 私はそれがあなたの質問に答えないことを知っていますが、あなたの質問は方向について言及していませんが、Google検索にはまだ役立つかもしれません
于 2014-12-02T15:35:41.923 に答える
1
ノード X から開始し、すべての子ノードを確認します (無向の場合、親ノードと子ノードは同等です)。これらの子ノードを X の子としてマークします。そのような子ノード A から、A の子である X' の子であるとマークします (X' は 2 歩離れているとマークされます)。後で X を押して X'' の子としてマークした場合、X は 3 ノード サイクルにあることを意味します。その親へのバックトラックは簡単です (そのままでは、アルゴリズムはこれをサポートしていないため、X' を持つ親を見つけることができます)。
注: グラフが無向であるか、双方向のエッジがある場合、サイクルで同じエッジを 2 回トラバースしたくないと仮定すると、このアルゴリズムはより複雑になります。
于 2009-02-13T16:47:42.310 に答える
1
グラフ内のすべての基本回路を見つけたい場合は、JAMES C. TIERNAN による EC アルゴリズムを使用できます。これは 1970 年以降の論文に掲載されています。
非常に独創的な EC アルゴリズムを php で実装することができました(間違いがないことを願っています)。ループがある場合は、ループも見つけることができます。この実装 (オリジナルのクローンを作成しようとする) の回路は、非ゼロ要素です。ここでのゼロは、存在しないことを表します (私たちが知っているように null です)。
以下のそれとは別に、アルゴリズムにさらに独立性を与える他の実装に従います。これは、ノードが負の数からでもどこからでも開始できることを意味します。たとえば、-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 に答える
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 に答える
0
開始ノード s から DFS を実行し、トラバーサル中に DFS パスを追跡し、s へのパスでノード v からエッジが見つかった場合はパスを記録します。(v,s) は DFS ツリーのバックエッジであるため、s を含むサイクルを示します。
于 2015-05-29T06:00:40.833 に答える
0
I stumbled over the following algorithm which seems to be more efficient than Johnson's algorithm (at least for larger graphs). I am however not sure about its performance compared to Tarjan's algorithm.
Additionally, I only checked it out for triangles so far. If interested, please see "Arboricity and Subgraph Listing Algorithms" by Norishige Chiba and Takao Nishizeki (http://dx.doi.org/10.1137/0214017)
于 2010-05-17T13:57:11.547 に答える
-1
于 2009-02-15T17:33:18.583 に答える