0

ルート ノード (Tarjan のインデックス 0) からの循環を、ルート ノードで開始および終了する無向マルチグラフにリストしたいと思います。

マルチグラフでのサイクル検出の指示を使用して、 Tarjanの強連結成分アルゴリズムを perlで記述しました。これは私のグラフです

V   E   E   E
1   2   3   4
2   1   3   
3   1   2   
4           1

私はこの結果を得る

1 root
3 2 1
------------
2 root
3 1 2
------------
3 root
2 1 3
------------
4 root
3 2 1 4
------------

インデックス 0 またはルートとして 4 が選択されている場合、3 2 1 4 の解でサイクルを完了するにはパスが 1 を 2 回通過する必要があるため、1 4 を返したいと思います。

ありがとうございました

4

1 に答える 1

0

Tarjanの強連結成分アルゴリズムを近隣検索で変更して、各ノードがエッジを共有するようにし、私のニーズを満たします。いくつかの解決策を省略します。

for each v in V do
 index := 0
 S := empty
    strongconnect(v)
repeat
...
while (w != v)
  if (loopcount = 0)
   w:=v
  else
   w := S.pop()
  end if
while (continuation = false)
 x := S.pop()
 for each (y, x) in E do
   if (y = w) then
     continuation = true
   end if
  repeat
  if (x = v) then
   continuation = true
 S.push(v)
 loopcount := loopcount+1
if(continuation = true)
  add x to current strongly connected component
endif
 repeat


        2   

8   3   1   6

    4       7
        5   

1   2   5   
2   3   6   1
3   4   2   8
4   3   5   
5   4   7   1
6   2   7   
7   5   6   
8           3



1 list
5 4 3 2 1 
------------
2 list
1 5 4 3 2 
------------
3 list
8 3 
------------
4 list
5 7 6 2 3 4 
------------
5 list
1 2 3 4 5 
------------
6 list
7 5 4 3 2 6 
------------
7 list
6 2 3 4 5 7 
------------
8 list
3 8 
------------
于 2013-03-16T08:01:42.840 に答える