は、現在の要素の処理にDFS異なるトポロジカルソートを

Question

はToplogicalソートの場合

• 、のみ、DFS異なるトポロジカルソートは、処理（出力に追加して再帰呼び出しの後に行われており再帰呼び出しの前に現在の要素の処理が行われます（つまり、 が出力キューに追加されます）。DFSの場合、再帰呼び出しの前に現在の要素が処理されます（つまり、 が出力キューに追加されます）。

は、これはあなたが見ることができるように、私は再帰呼び出しを行い、その後、最初の要素を印刷DFS

public void depthfirstsearchrecursive() 
    { 
     for(int i = 0;i<vertices.size();i++) 
     { 
      if(vertices.get(i).isVisited == false) 
      { 
       vertices.get(i).isVisited = true; 
       System.out.println(vertices.get(i).name + " "); 
       depthfirstsearchrecursiveUtil(vertices.get(i)); 
      } 
     } 
    } 
    public void depthfirstsearchrecursiveUtil(Vertex v) 
    { 
     for(int i = 0;i<v.neighbors.size();i++) 
     { 
      if(v.neighbors.get(i).isVisited == false) 
      { 
       v.neighbors.get(i).isVisited = true; 
       System.out.println(v.neighbors.get(i).name + " "); 
       depthfirstsearchrecursiveUtil(v.neighbors.get(i)); 
      } 
     } 
    } 

ための私のコードです。

これは、（再帰呼び出しが行われた後に行われるスタックにプッシュする、）ここに私のトポロジカルソートの実装

/* topological sort recursive */ 
    public void topologicalsortrecursive() 
    { 
     Stack<Vertex> output = new Stack<Vertex>(); 
     for(int i = 0;i<vertices.size();i++) 
     { 
      if(vertices.get(i).isVisited == false) 
      { 
       vertices.get(i).isVisited = true; 
       topologicalsortrecursiveDriver(vertices.get(i), output); 

//    System.out.println(vertices.get(i).name + " "); 
       output.push(vertices.get(i)); 
      } 
     } 
    } 
    public void topologicalsortrecursiveDriver(Vertex v, Stack<Vertex> output) 
    { 
     for(int i = 0;i<v.neighbors.size();i++) 
     { 
      if(v.neighbors.get(i).isVisited == false) 
      { 
       v.neighbors.get(i).isVisited = true; 
       topologicalsortrecursiveDriver(v.neighbors.get(i), output); 

//    System.out.println(v.neighbors.get(i).name + " "); 
       output.push(v.neighbors.get(i)); 
      } 
     } 
    } 

、処理

が、それは本当のことを言うことです、ある

• DFSはPreOrderトラバーサルと似ていますが、ここでは という要素を処理しますが、

Answer 1

（私は 逆後順を言った理由である）トポロジカルソートは、スタックに にそれらを押すことで、我々は最初の子供たちに を移動し、現在の要素を処理する逆ポスト順トラバーサル、のようなものです

正確ではありません。 DFSは一般的な形式です。これを使用して、事前評価および/または発注評価を実装することができます。

トポロジカルソートには、評価後のDFSが必要です。

は、次のコードを考えてみましょう：

void DFS(Vertex v) { 
    if (v.hasVisited) 
    return; 
    v.hasVisited = true; 
    doBeforeDepth(v) 
    for (Vertex u : v.neighbours) 
    DFS(u); 
    doAfterDepth(v); 
} 

void DFS() 
{ 
    for (Vertex v : vertices) 
     DFS(v); 
} 

あなたはトポロジカルソートを実行するには、このDFSコードを使用することができます。