Topological sorting is the result you get when you sort the tree in order of decreasing finishing times. What this means is that you run the Depth First Search algorithm and once it’s complete, you’ll have two sets of values: discovery times and finishing times. Finishing times sorted in reverse will generate the topologically sorted list.

DFS starts traversing the tree at vertex A. Since it has been discovered, we’ll mark it with the number 1. Number 1 is used to indicate that it has been discovered first.

The algorithm checks all the unvisited nodes from vertex A. Vertex A is connected to the unvisited nodes B and C. The DFS algorithm visits vertex B next. Vertex B is marked as visited and receives a discovery time of 2.

The algorithm checks all the unvisited nodes from vertex B. Vertex B is connected to the unvisited nodes C and D. The DFS algorithm visits vertex C next. Vertex C is marked as visited and receives a discovery time of 3.

The algorithm checks all the unvisited nodes from vertex C. Vertex C is connected to the unvisited nodes E and F. The DFS algorithm visits vertex E next. Vertex E is marked as visited and receives a discovery time of 4.

Vertex E does not have any additional edges that are connected to unvisited nodes. It backtracks to vertex C. With the backtrack, vertex E receives a finishing time of 5. The finishing time, 5, is displayed after the discovery time of 4.

The algorithm checks all the unvisited nodes from vertex C again. Vertex C is connected to the unvisited node F. The DFS algorithm visits vertex F next. Vertex F is marked as visited and receives a discovery time of 6.

Vertex F does not have any additional edges that are connected to unvisited nodes. It backtracks to vertex C. With the backtrack, vertex F receives a finishing time of 7. The finishing time, 7, is displayed after the discovery time of 6.

Vertex C does not have any additional edges that are connected to unvisited nodes. It backtracks to vertex B. With the backtrack, vertex C receives a finishing time of 8. The finishing time, 8, is displayed after the discovery time of 3.

The algorithm checks all the unvisited nodes from vertex B again. Vertex B is connected to the unvisited node D. The DFS algorithm visits vertex D next. Vertex D is marked as visited and receives a discovery time of 9.

Vertex D does not have any additional edges that are connected to unvisited nodes. It backtracks to vertex B. With the backtrack, vertex D receives a finishing time of 10. The finishing time, 10, is displayed after the discovery time of 9.

Vertex B does not have any additional edges that are connected to unvisited nodes. It backtracks to vertex A. With the backtrack, vertex B receives a finishing time of 11. The finishing time, 11, is displayed after the discovery time of 2.

Vertex A does not have any additional edges that are connected to unvisited nodes. It attempts to backtrack but has no additional nodes to backtrack to. With the backtrack, vertex A receives a finishing time of 12. The finishing time, 12, is displayed after the discovery time of 1. The DFS algorithm completes.

To get the discovery times list, you place the items in order of ascending discovery time.

To get the topologically sorted list, you place the items in order of descending finishing times. A was the last item to be marked as complete, so it goes in first, followed by B and then D. Although the first two elements were the same in both lists, element 3 changes from C to D. Next, vertex C was marked as complete, followed by vertices F and E. This completes the topologically sorted list.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.