Topological Sorting code example

Example 1: topological sorting

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end());
}

Example 2: 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 3: 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

Example 4: topological sort

def topological_sort():
    for each node:
        if visited[node] is False:
            dfs(node)
def dfs(node):
    visited[node] = True
    for nei in neighbours[node]:
        dfs(node)
    ret.insert_at_the _front(node)