Introduction to Directed Graph and Topological Sorting in Graph

Things to be discussed here,

• Directed Graph
• Topological Sorting
• Application of Topological Sorting
• Algorithm to find Topological Order
• Implementation in C++
• Practice Problems
• Summary

Prerequisite

• Checking Presence of Cycle in Directed Graph using DFS

Directed Graphs
A graph in which all the edges are directed is called a directed graph. In other words, if there is an edge from u->v then it means that you can go from u to v, but the reverse is simply not possible. Directed graphs are also called as digraphs.

Fig 1. Example of a Directed Graph

Classes of Directed Graphs:

• Acyclic Graphs
• There are no cycles in the graph, so there is no path from any node to itself.
• Successor Graphs
• The outdegree of each node is 1, so each node has a unique successor.

Topological Sorting

A topological sort is an ordering of the nodes of a directed graph such that if there is a path from node u to node v, then node u appears before node v, in the ordering. For example below is a directed graph.

For which one topological sort is { 4, 1, 5, 2, 3, 6 }.

Observation:

• An acyclic graph always has a topological sort.
• And if the graph contains cycle then it does not form a topological sort, because no node of the cycle can appear before the other nodes of the cycle in the ordering.
• The topological sort may not be unique i.e. graph can contain many topological sorts. For example when the graph with n nodes contains n connected component then we can n! topological sorts.

Application of Topological Ordering

• Job/ Activity scheduling depending on dependencies i.e. which/what should be done first.
• The topological ordering can also be used to quickly compute the shortest paths through a weighted directed acyclic graph.

Algorithm to find Topological  Sort
To find topological sort there are two efficient algorithms one based on Depth-First Search and other is Kahn's Algorithm. Here we will take look at Depth-First Search Approach and in a later article, we will study Kahn's Algorithm.

Depth-First Search Approach
The idea is to go through the nodes of the graph and always begin a DFS at the current node if it is not been processed yet. During the searches the nodes have three possible states:

• State 0: The node has not been processed yet ( blue )
• State 1: The node is under processing ( yellow )
• State 2: The node has been processed. ( green )

In the beginning, the state of all the nodes is 0. When the search reaches a node for the first time, its state becomes 1. Finally, after traversal of all its adjacent nodes of the node has been visited, its state becomes 2.

If the graph contains a cycle, we will find this out during the search, because sooner or later we will arrive at a condition where the node is in state 1. This means that we have already visited this node and again through some different path visiting the same node which means that we have found a cycle.

And if a graph contains a cycle then we can't find topological sort and if it does not contain a cycle then we construct topological sort by adding each node to list ones it is processed i.e. state becomes 2.  And then we reverse the list which gives us the topological sort.

Let us take an example to understand this fully, in this graph we start our depth-first search from node 1 to node 6.

Now, once we start our DFS from node 1, node 1 moves to state 1 and we explore its adjacent nodes which are 2 then 2 also moves to state 1, this again calls DFS on node 3, and then node 3 moves to state 1 which calls 6. Now there is no further call from 6 so it is processed, i.e. moved to state 2. And our list contains { 6 }. The yellow nodes are currently in state 1 and the green node is processed.

Now tracking back node 3 processed, then 2 processed, and then 1 processed. And our list contains

{ 6, 3, 2, 1 }. At this point, the next search begins at node 4. And 4 is added to state 1, visit 5 from where we cannot visit any other nodes as they are already been visited. So node 5 is moved to state 2.

And our list becomes { 6, 3, 2, 1, 5}, and finally 4 is also processed and added to this list. So our list now has { 6, 3, 2, 1, 5, 4}. From this, we observe that 6 is dependent on activity 1, 2, 3. i.e. it can be done only if 1, 2, 3 are already done. In the same way, 4 is independent of any other activity. And to represent this dependency, reverse the list, which looks like this on representation in the graph.

Note that the topological sort is not unique.

Implementation in C++
In this explanation, first I am checking whether the graph contains a cycle or not. As if the graph contains a cycle then there is no topological ordering. And if there is no cycle then we find the topological ordering.

• This algorithm is using DFS 2 times, once to check for a cycle and another for getting the reverse topological sort.
• The reverse() from STL is used to reverse the order value to get the topological sort.
• The time complexity of the algorithm is O( |V|+|E| ).

Practice Problems

1. Topological Sorting ( SPOJ )
2. Beverages ( UVA )
3. The Dueling Philosophers Problem ( ICPC Live Archive )
4. Ordering ( UVA )
5. Online Courses in BSU ( 770C )

That's all for this article, in the next session we will be discussing Dynamic Programming Application in Solving Some Classic Problems in Acyclic Graph and problems related to it and for now practice problems. ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA