-1

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

4

3 に答える 3

2

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

于 2009-03-14T19:57:48.807 に答える
1

おそらく、それを計算する最適な方法ではありませんが (それは です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---BAB
 | | | | \ / |\ /|
 | | | | X | X |
 | | | | / \ |/ \|
 D---C D---CCD

基本的に、頂点の順序付けられたすべてのセット (a、b、c、d) をチェックして、サイクルを形成できる 3 つの方法を確認します。

したがって、擬似コードは次のようになります。

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
于 2009-03-14T20:15:18.810 に答える
0

DFSが開始ノードを検出するすべてのノードとレコードノードに深さ制限深さ優先探索を適用します。検索については、ここの擬似コードを参照してください：http: //en.wikipedia.org/wiki/Depth-limited_search。次のようなものを追加する必要があります

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

ループの先頭まで。

于 2009-03-14T19:56:15.067 に答える