Topological Sorting using Source removal algorithm

What is topological sorting?

A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another.

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 0 3 1″. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no in-coming edges).

Source Removal Algorithm:

This is a direct implementation of the decrease and conquers method. Following are the steps to be followed in this algorithm-

1. From a given graph find a vertex with no incoming edges. Delete it among with all the edges outgoing from it. If there are more than one such vertices then break the tie randomly.
2. Note the vertices that are deleted.
3. All these recorded vertices give a topologically sorted list.

Question:

Answer:

Choose vertex B, because it has no incoming edge, delete it along with its adjacent edges.

According to the above steps remove the nodes and put it into a list.

Hence the list after topological sorting will be B, A, D, C, E.

How to find in-degree of each node?
There are 2 ways to calculate in-degree of every vertex:
Take an in-degree array which will keep track of
1) Traverse the array of edges and simply increase the counter of the destination node by 1.

for each node in Nodes
    indegree[node] = 0;
for each edge(src,dest) in Edges
    indegree[dest]++

Time Complexity: O(V+E)

2) Traverse the list for every node and then increment the in-degree of all the nodes connected to it by 1.

for each node in Nodes
        If (list[node].size()!=0) then
        for each dest in list
            indegree[dest]++;

Time Complexity: The outer for loop will be executed V number of times and the inner for loop will be executed E number of times, Thus overall time complexity is O(V+E).

The overall time complexity of the algorithm is O(V+E)

Reference: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/