Topological Sort and Cycle Detecting.

Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).The basic idea of coming up with a topological order lies on the fact that there is a source and a sink in the graph, i.e., its directed and acyclic. 

Topological Sorting vs Depth First Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. For example, in the given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting.

A DAG G has at least one vertex with in-degree 0 and one vertex with out-degree 0.
Proof: There’s a simple proof to the above fact is that a DAG does not contain a cycle which means that all paths will be of finite length. Now let S be the longest path from u(source) to v(destination). Since S is the longest path there can be no incoming edge to u and no outgoing edge from v, if this situation had occurred then S would not have been the longest path
=> indegree(u) = 0 and outdegree(v) = 0

Hence the idea that topological sort cannot be done for a cyclic directed graph can be used to check whether the given graph is cyclic or not.

The idea is to simply use Kahn’s algorithm for Topological Sorting

Steps involved in detecting cycle in a directed graph using BFS.

Step-1: Compute in-degree (number of incoming edges) for each of the vertex present in the graph and initialize the count of visited nodes as 0.

Step-2: Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue operation)

Step-3: Remove a vertex from the queue (Dequeue operation) and then.

1. Increment count of visited nodes by 1.
2. Decrease in-degree by 1 for all its neighboring nodes.
3. If in-degree of a neighboring nodes is reduced to zero, then add it to the queue.

Step 4: Repeat Step 3 until the queue is empty.

Step 5: If count of visited nodes is not equal to the number of nodes in the graph has cycle, otherwise not.

Following is the code implementation:-

The graph is being considered to be constructed already, do read the following post to know more: Graph Notations

void printTopologicalOrder()

{

    //Assuming nodes in 0-indexing 0->n-1

    //n=no. of nodes, adj-> adjacency list representation of graph

    vector<int>inDegree(n,0);

    //updating in degree for each node:

    for(auto x:adj) for(auto y:x) inDegree[y]++;

    queue<int>q;

    for(int i=0;i<n;i++) if(inDegree[i]==0) q.push(i);

    vector<int>topo; //to store the topological order

    int s=0; //to store count of visited nodes

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        topo.push_back(x);

        for(auto it:a[x])

            if(--inDegree[it]==0) q.push(it);

        s++; // incrementing visited nodes

    }

    if(s==n) //print topo

    else cout<<"The Graph is cyclic";

}

I have tried to keep the code as compact as possible, if u have any doubts, do let us know.

Practice Problem:

Course Schedule

Thanks for reading :)

________________________________________________________________