グラフの閉じたパスを見つけるための擬似コード

Question

私は、対応するadjMat [i、j] = 1に1をつけることによってノード間のエッジを追跡するグラフのための隣接行列を持っています。 このadjaceny行列を通して、私はグラフに存在する長さ4のすべての閉じたパスを探したいと思っています。誰でも私に擬似コードを提供してください。ありがとうございます。

Answer 1

DFSが開始ノードを検出するすべてのノードとレコードノードに深さ制限深度優先検索を適用します。 検索には、こちらの疑似コード：http://en.wikipedia.org/wiki/Depth-limited_searchを参照してください。ループの先頭に

if(node' == node && node'.depth==4) memorize(node) 

のようなものを追加するだけです。

Answer 2

これは宿題のように聞こえるので、私はすべてを遠ざけることはしません。しかし、ここではヒントがあります。長さ4のサイクルを見つけることに興味があるので、隣接行列の4乗を取って対角線に沿ってスキャンします。エントリM [i、i]が非ゼロである場合、頂点iを含むサイクルが存在する。

Answer 3

は、おそらくそれは（それがO(n^4)だ）、それを計算するための最適な方法ではありませんが、非常に簡単な方法は、あなたが次のサイクルごとにチェックし確認することができ、すべての頂点

a, b, c, d such that b > a, c > b, d > c 

をスキャンされます。

 
1. ([a,b] && [b,c] && [c,d] && [d,a]) 
2. ([a,b] && [b,d] && [d,c] && [c,a]) 
3. ([a,d] && [d,b] && [b,c] && [c,a]) 

1:   2:  3: 
A---B  A---B  A B 
| |  \/ |\ /| 
| |  X  | X | 
| |  /\  |/ \| 
D---C  D---C  C D 

あなたは基本的に、彼らはサイクルを形成することができる3つの方法のための頂点のすべての順序集合（A、B、C、D）をチェックしています。

ので、擬似コードは次のようになります。

for a = 0 to <lastVertex> 
for b = a + 1 to <lastVertex> 
    for c = b + 1 to <lastVertex> 
    for d = c + 1 to <lastVertex> 

    if(IsCycle(a,b,c,d)) AddToList([a,b,c,d]) 
    if(IsCycle(a,b,d,c)) AddToList([a,b,d,c]) 
    if(IsCycle(a,c,b,d)) AddToList([a,c,b,d]) 

    next d 
    next c 
next b  
next a