graph for topological sort code example

Example 1: topological sort

void dfs_helper(T src, map<int,bool>& visited, list<T> &ordering) { 
    //Recursive function that will traverse the graph 
         
    visited[src] = true; 
    //go to all nbr of that node that is not visited 
    for(T nbr:l[src]) { 
        if(!visited[nbr]) { 
            dfs_helper(src,visited,ordering);
        } 
    } 
    ordering.push_front(src);
} 

int dfs(T src) { 
        map<int,bool> visited; 
        list<T> ordering;
        //Mark all nodes as not visited. 
        //l = adjacency list implemented using std::unordered_map
        for(auto p:l) { 
            T node = p.first; 
            visited[node] = false; 
        } 

        for(auto p:l) {
            T node = p.first;
            if(!visited[node]) {
                dfs_helper(node,visited,ordering);
            }
        }

        //Finally print the list
        for(auto node:ordering) {
            cout << node << endl;
        }
}

Example 2: Topological sort

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L