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