Topological Sort examples provide the linear ordering of the vertices. According to topological sort, if there is an edge in the diagram going from vertex ‘A’ to vertex ‘B’, then ‘A’ comes before ‘B’ in the ordering”.
Topological Sorting can be applied if and only if the graph is a Directed Acyclic Graph.
For one directed acyclic graph, more than one ordering sequence may exist.
Keep in mind that a directed Acyclic Graph is a graph having no graph cycles and is labeled with directed arrows.
Steps to Find the Topological Ordering
First, find the vertex which having the least in-degree.
Second, Remove the least in-degree vertex along with its associated edges
Update the in-degree of the rest of the vertices.
Interlink all the removing (least in-degree) vertices in the order as they are removed from the directed acyclic graph.
In-degree: Number of vertices incoming toward a edge is called its in-degree.
Example of Topological Sort
Problem: Find all possible topological orderings for the given directed acyclic graph
Solution:
Step-01: Write in-degree of each vertex
Step-02: As vertex-A holds the least in-degree, remove it along with its associated edges and update the rest of the graph
Step-03:As vertex-B holds the least in-degree, remove it with its associated edges and update the rest of the graph
Step-04: There are two vertices with the similar least in-degree. So, there are two possible cases.
Case-01
Remove vertex-C before vertex-D
Case 02
Remove vertex-D before vertex-C
Above, both cases are valid, as given under
Step-05:Now, the above two cases will run separately parallel.
In case 01:
As vertex-D holds the least in-degree, remove it with its associated edges
The Last vertex-E is separated already by separating the second-last vertex-D.
In case-02:
As vertex-C holds the least in-degree, remove it with its associated edges
Step 06: As the Last vertex-E is separated already by separating the second-last vertex-C. So attach E to the last part of the ongoing ordering.
Result:
For the given directed acyclic graph, the following two different topological orderings are possible.
