1

開始ノードを選択してからDFSを介して続行することにより、重み付けされていない非巡回有向グラフをトラバースする特定のグラフアルゴリズムがあるかどうか知りたいです。検索されていない先行ノードがあるノードが検出された場合、開始するすべてのパスが探索されるまで、着信パスをバックトラックする必要があります。

グラフアルゴリズムのウィキペディアカテゴリを見つけましたが、ここにはアルゴリズムの小さな海があり、それらのほとんどに精通していません。

編集：例：グラフ{AB、EB、BC、BD}が与えられた場合、{A、B、E、B、C、D}としてトラバースするか、{A、B、E、C、D}として一意の順序でトラバースします。BFSやDFSとは異なり、このアルゴリズムは、最初の開始ノードのすべてのパスが使い果たされた場合に、新しい開始ノードで再開する必要がないことに注意してください。

4

3 に答える 3

2

あなたが探しているのはトポロジカルソートです。私の知る限り、事前計算なしでトポロジカルソートされた順序でグラフをトラバースする簡単な方法はありません。

トップソートを取得する標準的な方法は、標準のDFSを実行してから、訪問したノードを訪問時間順に保存することです。最後に、それらのノードを逆にして出来上がり、あなたはあなたが望む順序でそれらを持っています。

擬似コード：

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

リストtopsortには、希望する逆の順序で頂点が含まれます。それを修正するには、topsortの要素を逆にするだけです。

于 2010-02-24T00:44:40.687 に答える
2

DFSでは、通常、uで始まるエッジに基づいて、uの後にアクセスする頂点を選択します。最初にuで終わるエッジに基づいて選択します。これを行うには、転置グラフ情報を取得し、最初にそこから頂点を取得しようとします。

これは次のようになります。

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)
于 2010-02-24T01:04:31.973 に答える
2

を探している場合は、隣接リスト（または時間内に前処理できるエッジのリスト）topological sortを指定して、これを行うこともできます。(u,v)O(E)

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

adjacency list（またはエッジのリスト）が与えられた場合(u,v)、これはです。これはO( V + E )、各エッジが2回タッチされるためです。1回はインクリメント、1回はデクリメントしますO(1)。通常のキューでは、各頂点もキューによって最大2回処理されます。これはO(1)、標準のキューでも実行できます。

これは、フォレストを処理するという点でDFS（少なくとも単純な実装）とは異なることに注意してください。

もう1つの興味深い注意点は、ある種の構造/順序を課すことで置き換えるqueueと、実際にある順序でソートされた結果を返すことができるということです。priority_queue

たとえば、正規のクラス依存関係グラフの場合（クラスYを取得した場合にのみクラスXを取得できます）：

100:
101: 100
200: 100 101
201: 
202: 201

結果として、おそらく次のようになります。

100, 201, 101, 202, 200

ただし、常に小さい番号のクラスを最初に取得するように変更した場合は、次のように簡単に変更できます。

100, 101, 200, 201, 202
于 2010-02-24T02:17:43.307 に答える