Topological sort on a directed acyclic graph

Contents:

1. What is Topological Sorting ?
2. Illustration with the help of an example.
3. Implementation of topological sort in C++.

---

1. What is Topological Sorting ?
   In Acyclic Directed Graph G(E, V), Topological sorting is the ordering of vertices(V) of G in such a way that if vertex u is directed to vertex v then u should come first in this ordering and after that vertex v. There can be many valid topological sorts of a single directed acyclic graph(DAG in short). There are also many ways to implement topological sort algorithm but here we will slightly modify our DFS algorithm to do Topological Sorting.
   If you don't know DFS algorithm you must read this post.
2. Illustration with the help of an example :
   
   
   There can be many topological sorting of this DAG but i am writing only 3:
   
   • 1, 2, 4, 5, 3, 6, 7
   • 1, 2, 4, 3, 5, 6, 7
   • 1, 5, 7, 4, 6, 3, 2
   You can check the validity of this sorting by checking any 2 connected vertices(direct or indirect)(direction : u to v) then u must be present before v.
3. Implementation of topological sort in C++ :
   Logic : Let tSort[ ] stores the topological order of the above DAG G.
   Start dfs from node 1. (node 1) → (node 4) → (node 6)
   ! Note that 6 has no more unvisited neighbours, so store 6 in tSort i.e. tSort = {6, }.
   Now continuing our DFS, [Backtrack to node 4]
   (node 4) → (node 3)
   tSort = {6, 3, } Why ? follow !Note above [Backtrack to node 4]
   tSort = {6, 3, 4, }[Backtrack to node 1]
   (node 1) → (node 2)
   tSort = {6, 3, 4, 2, }[Backtrack to node 1]
   (node 1) → (node 5) → (node 7)
   tSort = {6, 3, 4, 2, 7, }[Backtrack to node 5]
   tSort = {6, 3, 4, 2, 7, 5, }[Backtrack to node 1]
   tSort = {6, 3, 4, 2, 7, 5, 1}
   Done !
   Reverse this array and you will get one of the valid topological sort of G.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

   #include<bits/stdc++.h> using namespace std; const int N = 100000; // Maximum number of nodes, change according to constraints. map<int, vector<int> > adjList; bool visited[N]; vector<int> tSort; void dfs(int u){ visited[u] = true; for(int i = 0 ; i < adjList[u].size() ; i ++){ int v = adjList[u][i]; // neighbour of u if(visited[v] != true){ // checking if neighbour is already visited or not dfs(v); } } tSort.push_back(u); // push in tSort[] only when it has no unvisited node left. } int main(){ memset(visited, 0, sizeof(visited)); int n , edges; // n = number of nodes, edges = Number of edges scanf("%d%d",&n,&edges); for(int i = 0 ; i < edges ; i ++){ int u, v; scanf("%d%d",&u,&v); // u -> v adjList[u].push_back(v); } for(int i = 1 ; i <= n ; i++){ if(!visited[i]){ dfs(i); } } reverse(tSort.begin(), tSort.end()); // Reversing tSort[] printf("Topological Sorting of DAG G is :\n"); for(int i = 0 ; i < tSort.size() ; i ++){ printf("%d ",tSort[i]); } printf("\n"); }

Thanks for reading this post !

The end !