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

Question

Is Topological sort different from DFS only in that,

• In case of Toplogical sort, the processing (adding to an output stack) of current element is done after recursive call, whereas,
• In case of DFS, the current element is processed (that is, printed or added to an output queue) before the recursive call?

This is my code for 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));
            }
        }
    }

As you can see, I print the element first, then, make the recursive call.

This is my Topological sort implementation

/* 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));
            }
        }
    }

Here, the processing (pushing into a stack, is done after the recursive call is made)

Is it true to say that,

• DFS is like a PreOrder traversal, where we process the element, then go to it's children, whereas,
• Topological sort is like a reverse Post order traversal, where we go to children first, and then process the current element, by pushing them to a stack, (which is why I said reverse Postorder)

Answer 1

Not exactly. DFS is the generic form. You can use it to implement a pre and/or post order evaluation.

Topological sort requires a post evaluation DFS.

Consider the following code:

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);
}

You can use this DFS code to perform topological sort.