Skip to content

Topological Sort

O(V+E) , O(V)

  • Directed Acyclic Graph (DAG)
  • for every directed edge uv, vertex u comes before v in the ordering.
  • first element -> in-degree as 0 (a vertex with no incoming edges).
  • can be more than one sorting
  • different from DFS

Application

  • Instruction scheduling
  • ordering of formula cell evaluation when recomputing formula values in spreadsheets
  • logic synthesis,
  • determining the order of compilation tasks to perform in makefiles
  • data serialization
  • resolving symbol dependencies in linkers
sortUtil(int v, bool visited[], stack<int> &Stack){
    visited[v] = true;

    list<int>::iterator i;
    for(i = adj[v].begin(); i!=adj[v].end(); ++i){
        if(!visited[v])
            sortUtil(v, visited, Stack);
    }

    Stack.push(v);
}

topologicalSort(int v){
    stack<int> Stack;

    bool *visited = new bool[V];
    for(int i = 0; i<V; i++)
        visited[i] = false;

    for(int i=0;i<V;i++)
        if(visited[i]==false)
            sortUtil(i, visited, Stack);

    while(Stack.empty() == false){
        cout << Stack.pop() << " ";
        Stack.pop();
    }
}