1

DAGグラフを検索する必要がありますが、ノードを指すリンクを向けている他のすべてのノードを確認する前に、ノードを通過したくありません。

この特定の状況を処理するための既存のアルゴリズムはありますか？深さ優先探索と幅優先探索は、このトラバーサルの順序では機能しません。

すなわち：

A -> B
B -> C
C -> D
A -> C

BとCの両方を見る前にDに到達したくありません。

4

5 に答える 5

2

あなたが探しているのは、カーン（1962）のトポロジカルソートアルゴリズムです。これは、現在BGLに実装されているトポロジカルソートアルゴリズムではありません。DFSベースであり、すべての頂点にアクセスし、トポロジカルの逆順で結果を出力しますが、BFSと非常によく似ており、説明した方法で頂点にアクセスします。第一段落。トラバーサルは自分で作成する必要がありますが、アルゴリズムは単純です。

トポロジカルソートウィキペディアのエントリにリストされている最初のアルゴリズムを参照してください：http：//en.wikipedia.org/wiki/Topological_sorting。Sedgewickの「AlgorithmsinC」のプログラム19.8も参照してください。

ヒント1：補助データ構造を使用して、各頂点のエッジの数を維持します。実際には、「グラフからエッジを削除する」部分は実行しないでください。

ヒント2：GPLV3で動作する例については、CoFlo制御フローグラフの生成および分析プロジェクトでのカーンのアルゴリズムの実装、具体的にはファイルtopological_visit_kahn.hをご覧ください：http：//coflo.svn.sourceforge .net / viewvc / coflo / trunk / src / controlflowgraph / topological_visit_kahn.h？view = log

于 2011-09-24T21:52:35.730 に答える
1

したがって、私の最新の考えは、エッジが追加または削除されるたびにグラフ全体でトポロジカルソートを実行し、各ノードでトラバースされる直接の子ノードの順序を保存することです（これは書くのが少し難しいアルゴリズムかもしれません）。

次に、変更された幅優先探索を実行し（カオスによって示唆されているように）、次のbfs擬似コードで次の行を変更します。

for each vertex v in Adj[u]

することが：

for each vertex v in OrderedAdj[u]

擬似コード：

BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
  end for
  color[s] := GRAY 
  d[s] := 0 
  ENQUEUE(Q, s)
  while (Q != Ø) 
    u := DEQUEUE(Q)
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY 
        d[v] := d[u] + 1  
        p[v] := u  
        ENQUEUE(Q, v)
      else
        if (color[v] = GRAY) 
          ...
        else 
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)

これはこれを達成するための最適な方法だと思いますが、独自のbfsトラバーサルアルゴリズムを記述し、さらに各ノードのノードの順序を保存し（回避したいと思っていたメモリのオーバーヘッド）、独自のdfsビジターを記述します。順序を見つけて、これをキャッシング段階のノードに保存します。

ただし、これを行う既存の方法がないことに驚いています。これは、ダググラフをナビゲートするかなり一般的な方法のように思われるためです...

于 2009-10-08T09:35:24.603 に答える
0

通常のグラフトラバーサルアルゴリズムではそれを行うことはできません。アルゴリズムが、独自の要件に違反する可能性がなければトラバースできないグラフ構造の知識を魔法のように持っている必要があるためです。最初にどのノードが他のどのノードからの接続を持っているかを示す後方ツリーを構築する2パスアプローチを使用する必要があります。次に、最初のパスからの情報を使用して必要に応じてトラバーサルを遅らせる修正幅優先探索を実行します。そして、いくつかのグラフ構造が2番目のパスをデッドロックする可能性があると思います。

于 2009-10-07T16:07:22.263 に答える
0

最初にトポロジカルソートを実行してから、ソートされたグラフに対して深さ優先探索を実行するのはどうですか？

それはうまくいくでしょうか？

于 2009-10-07T16:10:24.737 に答える
0

すべてのDAGには、少なくとも1つのリーフノードがあります。リーフノードノードとすべての着信アークを削除すると、別のDAGが残ります。再帰的に、この小さいDAGには少なくとも1つのリーフノードもあります。この方法ですべてのノードを再帰的に削除することにより、最終的にルートノードはリーフノードになります。

ここで、ノードを削除した順序を逆にすると、目的のプロパティを持つトラバーサル順序になります。最後にリーフノードにアクセスすることで、すべての親ノードを最初に確認したことを保証します。

于 2009-10-08T08:39:36.387 に答える