Topological Sorting

Topological Sorting

The topological sorting for a directed acyclic graph is the linear ordering of vertices. For every edge U-V of a directed graph, the vertex u will come before vertex v in the ordering.

Topological Sort is a linear ordering of the vertices in such a way that if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’, then ‘u’ comes before ‘v’ in the ordering.

It is important to note that-

• Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.
• There may exist multiple different topological orderings for a given directed acyclic graph.

Few important applications of topological sort are-

• Scheduling jobs from the given dependencies among jobs
• Instruction Scheduling
• Determining the order of compilation tasks to perform in makefiles
• Data Serialization

Example:

The topological orderings of the above graph are found in the following steps-

1. Write in-degree of each vertex-

2.      Vertex-A has the least in-degree. So, remove vertex-A and its associated edges. Now, update the in-degree of other vertices.

3.      Vertex-B has the least in-degree. So, remove vertex-B and its associated edges. Now, update the in-degree of other vertices.

4.      There are two vertices with the least in-degree. So, following 2 cases are possible-

In case-01,

Remove vertex-C and its associated edges. Then, update the in-degree of other vertices.

Remove vertex-D since it has the least in-degree. Then, remove the remaining vertex-E.

In case-02,

Remove vertex-D and its associated edges. Then, update the in-degree of other vertices.

Remove vertex-C since it has the least in-degree. Then, remove the remaining vertex-E.