Topological sort using DFS without recursion

Question

I know the common way to do a topological sort is using DFS with recursion. But how would you do it using stack<int> instead of recursion? I need to obtain the reversed post-order but I'm kinda stuck:

The graph is a vector<vector<int> > adjacency list

The following is the DFS which I want to use for topological sort

bool visited[MAX]={0};
stack<int> dfs, postOrder;
vector<int> newVec;
vector<int>::iterator it;

for(int i=0;i<MAX;i++){
    if(visited[i]==false){
        dfs.push(i);
    }   
    while(!dfs.empty()){
        int node=dfs.top();
        dfs.pop();
        visited[node]=true;
        newVec=graph[node]; //vector of neighboors
        for(it=newVec.begin();it!=newVec.end();it++){
            int son=*it;
            if(visited[son]==false){
                dfs.push(son);
            }
        }
    }
}

Answer 1

In order to construct the postOrder list you need to know the time when your algorithm has finished processing the last child of node k.

One way to figure out when you have popped the last child off the stack is to put special marks on the stack to indicate spots where the children of a particular node are starting. You could change the type of your dfs stack to vector<pair<bool,int>>. When the bool is set to true, it indicates a parent; false indicates a child.

When you pop a "child pair" (i.e. one with the first member of the pair set to false) off the stack, you run the code that you currently have, i.e. push all their children onto the stack with your for loop. Before entering the for loop, however, you should push make_pair(true, node) onto the stack to mark the beginning of all children of this node.

When you pop a "parent pair" off the stack, you push the parent index onto the postOrder, and move on:

vector<vector<int> > graph;
vector<bool> visited(max);
stack<pair<bool,int>> dfs;
stack<int> postOrder;
for(int i=0 ; i < max ; i++){
    if(!visited[i]){
        dfs.push(make_pair(false,i));
    }   
    while(!dfs.empty()){
        pair<bool,int> node=dfs.top();
        dfs.pop();
        if (node.first) {
            postOrder.push(node.second);
            continue;
        }
        if (visited[node.second]) {
            continue;
        }
        visited[node.second]=true;
        dfs.push(make_pair(true, node.second));
        const auto& newVec=graph[node.second]; //vector of neighboors
        for(const auto son: newVec){
            if(!visited[son]){
                dfs.push(make_pair(false, son));
            }
        }
    }
}

Demo on ideone.

Answer 2

I think your code is a good non-recursive DFS . The key point of topological sort is that:

When you pick a node to push into the stack. This node must have no precessor( has a in-degree of 0). This means you are doing a DFS base on in-degree in stead of push all the adjacent nodes into the stack, you always pick the one with 0 in-degree

So you push every node that have no precessor in the stack. Pop one, print it and remove it from all its adjacent nodes' precessor list ( or decrease its adjacent nodes' in-degree by 1). This need you to edit your adjacent list. Than push all its adjacent nodes that has in-degree of 0 now in to the stack( this phase may fail but no problem, you still got some nodes in the stack). Then pop the next one. Repeat until the stack is empty. The node sequence that you printed is the topological sort result of the graph.

Answer 3

Iterative topological sort. Using stack and colorizing graph nodes: 0 - not visited, 1 - in progress, 2 - done. With built-in check whether graph has cycles or not. This approach doesn`t need extra states ("anchors") in stack (like in this solution) with info about should we add current node to the answer or not.

Try sample.

void dfs(const unordered_multimap<int, int>& graph, vector<int>& color, int node, const function<void(int)> post_order_func)
{
  stack<int> nodes;
  nodes.push(node);

  while (!nodes.empty())
  {
    int from = nodes.top();

    if (color[from] == 1)
    {
      color[from] = 2;
      post_order_func(from);
      nodes.pop();
      continue;
    }
    else if (color[from] == 2)
    {
      nodes.pop();
      continue;
    }

    color[from] = 1;
    auto range = graph.equal_range(from);

    for (auto it = range.first; it != range.second; ++it)
    {
      const auto& to = it->second;
      if (color[to] == 0)
      {
        nodes.push(to);
      }
      else if (color[to] == 1)
      {
        throw runtime_error("Graph has cycle. Topological sort impossible.");
      }
    }
  }
}

void topological_sort(int n, const unordered_multimap<int, int>& graph, vector<int>& result)
{
  result.resize(n);

  vector<int> color(n, 0);
  int j = 0;
  auto post_order_func = [&result, &j](int node) {
    result[j++] = node;
  };

  for (int i = 0; i < n; ++i)
  {
    if (color[i] == 0)
    {
      dfs(graph, color, i, post_order_func);
    }
  }

  reverse(begin(result), end(result));
}

Answer 4

The node is 1st visited and is still in process, it's added to stack as false. These nodes are then processed from stack as LIFO, and changed to true (processed means children visited). After all children processed, while tracing path back, this node dropped from stack.

For those trying to implement this code, visited[node.second]=true; should be moved to the 2 places where node is 1st added to stack as false. This, so that back edges leading to already traced vertices not revisited.

Answer 5

Below is my iterative code to topological sorting of DAG.

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
using namespace std;

unordered_map<int, unordered_set<int>> g;  // this is the simplest graph representation I was able to implement. Map the vertices to their set of children

void addEdge(int x, int y) { // Add edges to the graph
    g[x].insert(y);
}

void topSort() {
    unordered_set<int> visited; // Keep track of visited nodes
    stack<int> mainStack; // The stack that will have the resulting vertices in topologically sorted order

    for(auto it = g.begin(); it != g.end(); it++) {
        if(visited.count(it->first) == 0) { // If the vertex was not already visited do the following
            visited.insert(it->first); // visit the vertex
            stack<int> locStack;
            locStack.push(it->first); // push it to local stack
            while(!locStack.empty()) { // This part is similar to basic DFS algorithm
                int curr = locStack.top();
                bool unVisCh = false; // Keep a boolean to check whether there is any unvisited child
                for(auto it2 = g[curr].begin(); it2 != g[curr].end(); it2++) {
                    int child = *it2;
                    if(visited.count(child) == 0) {
                        unVisCh = true;
                        visited.insert(child);
                        locStack.push(child);
                    }
                }
                if(!unVisCh) { // if there is no unvisited child then we can push the vertex to the resulting stack
                    locStack.pop();
                    mainStack.push(curr);
                }
            }
        }
    }

    while(!mainStack.empty()) {
        cout<<mainStack.top()<<" ";
        mainStack.pop(); // print them in order
    }
    cout<<endl;
}

int main() {
    addEdge(1,2);
    addEdge(4,5);
    addEdge(5,6);
    addEdge(3,2);
    addEdge(2,6);
    addEdge(1,3);
    addEdge(4,3); // add adges to the graph

    topSort();

    return 0;
}

For testing: ideone

Answer 6

Here is the code for Topological Sort in a Non Recursive manner in java. It is more or less like a DFS Approach with some additional code to attain the goal.

package com.adjacency.list;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node {
    public int data;
    public Node link;

    @SuppressWarnings("unused")
    private Node() {
    }

    public Node(int data) {
        this.data = data;
        this.link = null;
    }
}

class AdjacencyList {
    public Node head;

    public AdjacencyList() {
        head = null;
    }
}

public class Graph {
    private AdjacencyList[] adjacencyArray;
    private int numberOfVertices;

    boolean visited[];

    @SuppressWarnings("unused")
    private Graph() {
    }

    public Graph(int numberOfVertices) {
        this.numberOfVertices = numberOfVertices;
        this.adjacencyArray = new AdjacencyList[this.numberOfVertices];

        for (int index = 0; index < this.numberOfVertices; ++index) {
            this.adjacencyArray[index] = new AdjacencyList();
        }

        visited = new boolean[this.numberOfVertices];
    }

    public void addEdge(int fromVertex, int toVertex) {
        Node node = new Node(toVertex);

        if (adjacencyArray[fromVertex].head == null) {
            adjacencyArray[fromVertex].head = node;
        } else {
            node.link = adjacencyArray[fromVertex].head;
            adjacencyArray[fromVertex].head = node;
        }
    }

    private boolean hasNonVisitedNeighbour(int data) {
        Node iterator = adjacencyArray[data].head;
        while (iterator != null) {
            if (!visited[iterator.data]) {
                // System.out.println("Non visited node present");
                return true;
            }
            iterator = iterator.link;
        }
        return false;
    }

    private int nextNonVisitedNeighbour(int data) {
        Node iterator = adjacencyArray[data].head;
        while (iterator != null) {
            if (!visited[iterator.data]) {
                return iterator.data;
            }
            iterator = iterator.link;
        }
        return -1;
    }

    public void topologicalSort() {
        for (int index = 0; index < numberOfVertices; ++index) {
            visited[index] = false;
        }

        Stack<Integer> output = new Stack<Integer>();
        Stack<Integer> stack = new Stack<Integer>();

        for (int nodeInSequence = 0; nodeInSequence < numberOfVertices; ++nodeInSequence) {
            if (!visited[nodeInSequence]) {
                visited[nodeInSequence] = true;
                stack.push(nodeInSequence);

                while (!stack.isEmpty()) {
                    int node = stack.pop();

                    while (hasNonVisitedNeighbour(node)) {
                        stack.push(node);
                        node = nextNonVisitedNeighbour(node);
                        visited[node] = true;
                    }
                    output.push(node);
                }
            }
        }

        System.out.println("Topological Sort");
        System.out.println("-----------------");
        while (!output.isEmpty()) {
            System.out.println(output.pop());
        }
    }
}

Answer 7

The Graph structure is as folows

N: number of vertices adj[]: input graph

vector<int> topoSort(int V, vector<int> adj[]) {
    stack<int> s;
    vector<int> f(V,0);
    
    stack<int> out; 
    int i,j,x;
    for(i=0;i<V;i++){
        if(f[i]==0){
            s.push(i);
            
            while(!s.empty()){
                x = s.top();
                s.pop();
                if(f[x]==1){
                    out.push(x);
                    continue;
                }
                f[x] = 1;
                s.push(x);
                for(j=0;j<adj[x].size();j++){
                    if(f[adj[x][j]]==0){
                        s.push(adj[x][j]);
                    }
                }
            }
        }
    }
    
    vector<int> output;

    while(!out.empty()){
        x=out.top();
        out.pop();
        //cout << x << " ";
        output.push_back(x);
    }
    //cout << endl;
    
    return output;
}

Answer 8

I am not too much familiar with C++ that's why I am giving answers in JAVA.

The given answer is also a solution for LeetCode 210 problem.

In the Iterative method of DFS, we are backtracking when all neighbours of u node are already visited that's why we are poping the stack element and push it to the topological sort stack.

 class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            // Create graph
            Graph g = new Graph(numCourses);
            for(int i = 0; i < prerequisites.length; i++) {
                g.addEdge(prerequisites[i][1], prerequisites[i][0]);
            }
       
        // Detect Cycle
        if(g.isCycleExist()) {
            return new int[0];
        }
        
        // Apply Topological Sort
        Stack<Integer> stack = new Stack<Integer>();
        boolean[] visited = new boolean[numCourses];
        // apply dfs
        for(int i = 0; i < numCourses; i++) {
            if(!visited[i]) {
                g.iterativeDFS(i, visited, stack);
            }
        }
        int[] ans = new int[numCourses];
        int i = 0;
        while(!stack.empty()) {
            ans[i++] = stack.pop();
        }
        return ans;
    }
}


class Graph {
    private int v;
    private LinkedList<Integer> addList[];

    Graph(int vertices) {
        v = vertices;
        addList = new LinkedList[vertices]; 
        for(int i=0; i < vertices; i++) {
            addList[i] = new LinkedList<Integer>();
        }
    }

    void addEdge(int source, int destination) {
        addList[source].add(destination);
    }
    
    boolean isCycleExist() {
        int[] visited = new int[v];
        for(int u = 0; u < v; u++){
            if(visited[u] == 0) {
                if(isCycleUtil(u, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    boolean isCycleUtil(int u, int[] visited) {
        if(visited[u] == 1) { // already visited
            return true; // if we comes to a node which is in process that means its a loop.
        }
        if(visited[u] == 2) { // already processed
            return false; // as it is already procedd no need to procedd it again.
        }
        visited[u] = 1;   // Mark current as visited
        for(int v = 0; v < this.addList[u].size(); v++) {
                if(isCycleUtil(this.addList[u].get(v), visited)){
                    return true;
                }
        }
        visited[u] = 2; // Mark current node as processed
        return false;
    }
    
    void dfs(int u, boolean[] visited, Stack<Integer> stack) {
        visited[u] = true;
        for(int v=0; v< addList[u].size(); v++) {
            if(!visited[addList[u].get(v)]) {
                dfs(addList[u].get(v), visited, stack);
            }
        }
        stack.push(u);
    }
    
    void iterativeDFS(int i, boolean[] visited, Stack<Integer> topologicalStack) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(i);
        visited[i] = true;
        while(!stack.empty()) {
            int u = stack.peek();
             boolean isAllVisited = true;
             for(int v=0; v< addList[u].size(); v++) {
                if(!visited[addList[u].get(v)]) {
                    isAllVisited = false;
                    visited[addList[u].get(v)] = true;
                    stack.push(addList[u].get(v));
                    break;
                }
            }
            if(isAllVisited) {
                int x = stack.pop();
                topologicalStack.push(x);
            }
        }
    }
        
}

Answer 9

Here we go again. :-) I am submitting an answer, because I do not have enough points to make comments. :-(

Well let me say that I like this algorithm a lot. If the graph is defined in the right way, then there is no error. But take this graph:

vector<vector<int>> graph
{
     { 2, 1 }
    ,{ 2 }
    ,{ }
};

This will display: 2 1 2 0

To protect yourself from graphs defined in that way or where the edges that come in are random you can do this:

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    stack<pair<bool, int>> dfs;
    stack<int> postorder;
    vector<int> newvector;
    vector<int>::iterator it;
    vector<vector<int>> graph
    {
         { 2, 1 }
        ,{ 2 }
        ,{ }
    };

    vector<bool> visited(graph.size());
    vector<bool> finallyvisited(graph.size());

    for (int i = 0;i < graph.size();i++)
    {
        if (!visited[i])
        {
            dfs.push(make_pair(false, i));
        }

        while (!dfs.empty())
        {
            pair<bool, int> node = dfs.top();
            dfs.pop();
            if (node.first)
            {
                if (!finallyvisited[node.second])
                {
                    finallyvisited[node.second] = true;
                    postorder.push(node.second);
                    cout << node.second << endl;
                }
                continue;
            }

            visited[node.second] = true;
            dfs.push(make_pair(true, node.second));
            newvector = graph[node.second];
            for (it = newvector.begin();it != newvector.end();it++)
            {
                int son = *it;
                if (!visited[son])
                {
                    dfs.push(make_pair(false, son));
                }
            }
        }
    }
    return 0;
}

Or you could preorder the graph, maybe someone could show that solution. How to preorder randomly given edges that there is no need for second check. :-)

And I did though over the Atif Hussain comment and it is erroneous. That would never work. You always want to push down the stack a node as late as possible so it pops as first as possible.