Topological sorting in graphs with example

 Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.

Topological Sorting for a graph is not possible if the graph is not a DAG.

A simple algorithm to find a topological ordering is to find out any vertex with in-degree zero, that is, a vertex without any predecessor. We can then add this vertex in an ordering set and remove it along with its edges from the graph. Then we repeat the same strategy on the remaining graph until it is empty.

 1. Initially the indegree (v2) is zero; We can then add this vertex in an ordering set and remove it along with its edges from the graph.

2. After removing v2 from the graph; Next the indegree (v5) is zero; We can then add this vertex in an ordering set and remove it along with its edges from the graph.

3. After removing v5 from the graph; Next the indegree (v7) is zero; We can then add this vertex in an ordering set and remove it along with its edges from the graph.

4. After removing v7 from the graph; Next the indegree (v4) is zero; We can then add this vertex in an ordering set and remove it along with its edges from the graph.

5. After removing v4 from the graph; Next the indegree (v1,v6) is zero; you can select any one node from these, I am selecting node 1. We can then add this vertex in an ordering set and remove it along with its edges from the graph.

6. After removing v1 from the graph; Next the indegree (v6) is zero; We can then add this vertex in an ordering set and remove it along with its edges from the graph.

7. Now the graph contains a single node 3, which is then added into the ordering set and removed from the graph. The graph becomes empty.

8. Topological order is: v2-v5-v7-v4-v1-v6-v3



The topological ordering for a graph is not necessarily unique. For example, in the above process, in step-5, if you choose node 6, then the topological order is: v2-v5-v7-v4-v6-v1-v3