僅在當前元素的該處理從DFS不同拓撲排序是遞歸調用

在Toplogical排序的情況下的拓撲排序，處理（添加到輸出後進行堆棧）當前元素在遞歸調用後完成，而
在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遍歷，我們在那裏處理元素，然後去找它的孩子，而
拓撲排序就像是一個相反的帖子序遍歷，我們去哪裏孩子，然後再處理當前的元素，通過推動他們堆棧，（這就是爲什麼我說反向後序）

來源

2016-11-09 PepperBoy

不完全。 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代碼來執行拓撲排序。

來源

2016-11-09 15:09:42 Shloim

僅在當前元素的該處理從DFS不同拓撲排序是遞歸調用

回答

相關問題