DFSと同様のグラフアルゴリズムを必要とします

Question

DFS経由して進行し、その後、開始ノードを選択し、によって重み付けされていない非環式有向グラフをトラバース特定のグラフアルゴリズムがある場合は、

私は興味があります。ノードが未探索の前任者を持っていることに遭遇した場合、それは戻って検討されている起動するすべてのパスまでの着信パスを追跡する必要があります。

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

編集：例： グラフ{AB、EB、BC、BD}所与として、トラバース：として{A、B、E、B、C、D}または一意順序{A、B、E、C、D}。 なお、第1の開始ノードのすべてのパスが消耗している場合BFSまたはDFSとは異なり、このアルゴリズムは、新たなスタートノードで再び開始する必要はありません。

Answer 1

で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)

Answer 2

あなたが探していることはトポロジカルソートです。私は、任意の事前計算せずにそのトポロジー的にソート順にグラフをトラバースする簡単な方法はありません承知している限ります。

topsortを取得するための標準的な方法は、標準の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の要素を逆転ます。

Answer 3

は、あなたが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 )のリスト）を考えると、これは、O(1)あります。通常のキューでは、各頂点も二回、最大でキューによって処理されます - 。標準キューにO(1)でも行うことができます。

なお、DFSからこの異なる（少なくともストレートアップ実装）という点で、それは森林を処理する。

もう一つの興味深いメモは、構造/発注のいくつかの並べ替えを課すqueueでpriority_queueに置き換えた場合、あなたが実際の結果は、いくつかの順序でソート返すことができるということです。

たとえば、正規のクラスの依存関係グラフ（あなたはクラスYを取った場合にのみ、クラスXを取ることができます）のために

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

あなたはおそらく結果として、になるだろう

100, 201, 101, 202, 200

しかし、あなたは常に最初に小さい番号のクラスを受講することをので、それを変更した場合、あなたは簡単に返すためにそれを変更することができます：

100, 101, 200, 201, 202