Topological sort using DFS without recursion

algorithm, c++, depth-first-search, stack, topological-sort

Solution

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.

Problem

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

Original source