In this post, we are continuing with Graph series and we will discuss the Topological Sorting algorithm and some problems based on it.

Topological Sorting Algorithm is very important and it has vast applications in the real world. So, let’s start.

Directed Acyclic Graph

We have already discussed the directed and undirected graph in this post. So, now let’s discuss the cyclic and acyclic graph.

The simplest definition would be that if a Graph contains a cycle, it is a cyclic graph else it is an acyclic Graph.

In undirected graph, to find whether a graph has a cycle or not is simple, we will discuss it in this post but to find if there is a cycle present or not in a directed graph, Topological Sort comes into play.

Detect cycle in undirected Graph

Now let’s discuss how to detect cycle in undirected Graph. For that, let’s take an example,

Now let me ask you, what is the difference between the above two Graphs ..?

Yes, you guessed it right, the one in the left side is undirected acyclic graph and the other one is cyclic.

Why the graph on the right side is called cyclic ?

The reason is simple, there is at least two ways to reach any node of the cycle and this is the main logic to find a cycle in undirected Graph.

If an undirected Graph is Acyclic, then there will be only one way to reach the nodes of the Graph.

Algo to find Cycle in undirected Graph

To find cycle, we will simply do a DFS Traversal and also keep track of the parent vertex of the current vertex. If parent vertex is unique for every vertex, then graph is acyclic or else it is cyclic.

Let’s see the code,

unordered_map<int, vector<int>> adj;
bool detect(int s, bool vis[], int parent)
{
    vis[s] = true;
    for(auto i = adj[s].begin(); i != adj[s].end(); i++)
    {
        if(vis[*i] == false)
        {
            if(detect(*i, vis, s) == true)
                return true;
        }
        else if(*i != parent){
            return true;
        }
    }
    return false;
}

For every vertex, the parent will be the vertex from which we reach the current vertex.

Initially, parents will be -1 but accordingly, we will update the parent when we move ahead.

Hope, code, and logic is clear to you. Let’s move ahead.

Detect Cycle in Directed Graph

For directed Graph, the above Algorithm may not work. Let’s see how,

The above Directed Graph is Acyclic, but the previous algorithm will detect a cycle because vertex 1 has two parents (vertex 2 and vertex 3), which violates our rule.

Although the above-directed Graph is Acyclic, the previous algorithm will detect a cycle. So the Algorithm fails.

To detect a cycle in a Directed Acyclic Graph, the topological sort will help us but before that let us understand what is Topological Sorting?

Topological Sort

We have discussed many sorting algorithms before like Bubble sort, Quick sort, Merge sort but Topological Sort is quite different from them.

Topological Sort for directed cyclic graph (DAG) is a algorithm which sort the vertices of the graph according to their in–degree.

Let’s understand it clearly,

What is in-degree and out-degree of a vertex ?

Out–Degree of a vertex (let say x) refers to the number of edges directed away from x .

Similarly,  In-Degree of a vertex (let say y) refers to the number of edges directed towards y from other vertices.

Let’s see an example,

Hope, concept of in-degree and out-degree is clear to you.

Now in Topological Sorting, we sort the vertices of graph according to their In-degree.

Let’s take the same example to understand Topological Sorting,

Topological Sorting of above Graph : 2 3 1

Let’s take another example,

Topological Sorting of above Graph : 0 5 2 4 1 3 6

There may be multiple Topological Sort for a particular graph like for the above graph one Topological Sort can be 5 0 4 2 3 6 1, as long as they are in sorted order of their in-degree, it may be the solution too.

Hope, concept of Topological Sorting is clear to you. Now let’s discuss the algorithm behind it,

Topological Sorting Algorithm (BFS)

We can find Topological Sort by using DFS Traversal as well as by BFS Traversal. We will discuss both of them.

Let’s first the BFS approach to finding Topological Sort,

Step 1: First we will find the in degrees of all the vertices and store it in an array. Let’s discuss how to find in-degree of all the vertices.

For that, the adjacency list given us will help, we will go through all the neighbours of all the vertices and increment its corresponding array index by 1.

Let’s see the code,

unordered_map<int, vector<int>> adj;
int* topological_Sort(int V) 
{
    int in_degree[V] = {0};
    for(int i = 0; i < V; i++)
    {
     
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_degree[*itr]++;
    	}
    }
}

Step 2 : We will declare a queue, and we will push the vertex with in-degree 0 to it.

Step 3 : We will run a loop until the queue is empty, and pop out the front element and print it.

The popped vertex has the least in-degree, also after popping out the front vertex of the queue, we will decrement in-degree of it’s neighbours by 1.

It is obvious, removal of every vertex will decrement the in-degree of it’s neighbours by 1.

Step 4: If in-degree of any neighbours of popped vertex reduces to 0, then push it to the queue again.

Let’s see the above process,

unordered_map<int, vector<int>> adj;
int* topological_Sort(int V) 
{
    int in_degree[V] = {0};
    for(int i = 0; i < V; i++)
    {
     
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_degree[*itr]++;
    	}
    }
    queue<int> q;

    for(int i=0;i<V;i++) {
        if(in_degree[i] == 0) q.push(i);
    }

    while(!q.empty())
    {							            							        
        int p = q.front();
        q.pop();
        
        cout << p <<" ";
        
        for(auto itr = adj[p].begin(); itr != adj[p].end(); itr++)
        {
            in_degree[*itr]--;
            
            if(in_degree[*itr] == 0) q.push(*itr);
        }
    }
}

That’s it, the printed data will be our Topological Sort, hope Algorithm and code is clear.

Let’s understand it by an example,

in_degree[] for above graph will be, {0, 2, 1, 2, 1, 0, 2}. Now let’s move ahead,

The above pictorial diagram represents the process of Topological Sort, output will be 0 5 2 3 4 1 6.

Time Complexity : O(V + E)
Space Complexity : O(V)

Hope concept and code is clear to you. Let’s move ahead.

Cycle Detection in Directed Graph

Since we have discussed Topological Sorting, let’s come back to our main problem, to detect cycle in a Directed Graph.

Let’s take an simple example,

In the example above, graph on left side is acyclic whereas graph on right side is cyclic.

Run Topological Sort on both the Graphs, what is your result..?

For the graph on left side, Topological Sort will run fine and your output will be 2 3 1.

But for the graph on right side, Topological Sort will print nothing and it’s obvious because queue will be empty as there is no vertex with in-degree 0.

Now, let’s analyse why is it happening..?

Significance of vertex with in-degree 0

As observed for the above case, there was no vertex present in the Graph with in-degree 0.

This signifies that there is no vertex present in the graph which is not connected to atleast one other vertex. You know what is signifies..?

It signifies the presence of a cycle, because it can only be possible in the case of cycle, when no vertex with in-degree 0 is present in the graph.

Let’s take another example,

Again run Topological Sort for the above example,

If we run Topological Sort for the above graph, situation will arise where Queue will be empty in between the Topological Sort without exploration of every vertex.

And this again signifies a cycle. Hope you understood the concept behind it.

Let’s see the code,

unordered_map<int, vector<int>> adj;
int* topological_Sort(int V) 
{
    int in_degree[V] = {0};
    for(int i = 0; i < V; i++)
    {
     
        for(auto itr = adj[i].begin(); itr != adj[i].end(); itr++)
        {
             in_degree[*itr]++;
    	}
    }
    queue<int> q;

    for(int i=0;i<V;i++) {
        if(in_degree[i] == 0) q.push(i);
    }

    int cnt = 0;
    while(!q.empty())
    {							            							        
        int p = q.front();
        q.pop();
       
        cnt++;
        
        for(auto itr = adj[p].begin(); itr != adj[p].end(); itr++)
        {
            in_degree[*itr]--;
            
            if(in_degree[*itr] == 0) q.push(*itr);
        }
    }
    
    if(cnt != V) cout<<"Cycle Present\n";
    else cout<<"Cycle Not Present\n";
}

Hope code is simple, we are just counting the occurrence of vertex, if it is not equal to V, then cycle is present as topological Sort ends before exploring all the vertices.

Logic behind the Algorithm (MasterStroke)

The main logic of the above algorithm is that if there is a cycle present in a directed Graph, definitely a situation will arise where no vertex with in-degree 0 will be found because for having a cycle, minimum in-degree 1 is required for every vertices present in the cycle.

It’s obvious logic and hope, code and logic is clear to you all. Let’s move ahead.

Topological Sorting Algorithm (DFS)

Although this topic was not important as we have already discussed the BFS approach which is relatively easier to understand but sometimes in an interview, interviewer ask you to find Topological Sort by DFS approach. So it’s better to give it a look.

It is highly recommended to try it before moving to the solution because now you are familiar with Topological Sorting. So, give it a try for sure.

Let’s take the same example,

It’s clear in topological Sorting our motive is to give preference to vertex with least in-degree.

In other words, if we give preference to vertex with least out-degree and reverse the order of Topological Sort, then also we can get our desired result.

Let’s say, Topological Sorting for above graph is 0 5 2 4 3 1 6.

In above diagram number of out-degrees in written above every vertex.

If we sort it with respect to out-degree, one of the Topological Sort would be 6 1 3 4 2 5 0 and reverse of it will give you Topological Sort w.r.t in-degree.

Hope this is clear and this is the logic of this algorithm of finding Topological Sort by DFS.

Algorithm to find Topological Sort (DFS)

Step 1: Do a DFS Traversal and if we reach a vertex with no more neighbors to explore, we will store it in the stack.
2: Continue this process until DFS Traversal ends.

Step 3: Take out elements from the stack and print it, the desired result will be our Topological Sort. That’s it.

NOTE: Topological Sort works only for Directed Acyclic Graph (DAG).

Let’s see the code for it,

unordered_map<int,vector<int>> adj;
void f(int s, stack<int> &stack, bool vis[])
{
    vis[s] = true;
    for(auto i = adj[s].begin(); i != adj[s].end(); i++)
    {
        if(vis[*i]==false)
        {
            f(*i,stack,vis);
        }
    }
    stack.push(s);
}

void topological_Sort(int V) 
{
    bool vis[V] = {false};
    stack<int> s;
    
    for(int i=0;i<V;i++)
    {
        if(vis[i] == false)
        {
            f(i, s, vis);
        }
    }

    while(!s.empty())
    {
         cout << s.top() << " ";
         s.pop();
     }
}

Hope code is clear, it is simple code and logic is similar to what we have discussed before.

DFS Traversal sorts the vertex according to out-degree and stack is helping us to reverse the result. That’s it.

Time Complexity : O(V + E)
Space Complexity: O(V)

I hope you enjoyed this post about the topological sorting algorithm. We will continue with the applications of Graph. See you later in the next post.

That’s all folks..!!!Wiki