拓扑排序与DFS的区别仅在于当前元素的处理是在递归调用之后完成的

Question

拓扑排序与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遍历，我们处理元素，然后转到 children，而
拓扑排序就像是逆向Post顺序遍历，我们去哪里先到 children，然后处理当前元素，通过推送它们堆叠在一起，（这就是为什么我说 reverse Postorder）

Answer 1

不完全是。 DFS 是通用形式。您可以使用它来实施预 and/or post 订单评估。

拓扑排序需要 post 评估 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 代码执行拓扑排序。

拓扑排序与DFS的区别仅在于当前元素的处理是在递归调用之后完成的

Is Topological sort different from DFS only in that processing of current element is done after recursive call

java

recursion

graph

depth-first-search

topological-sort