Question

The chapter suggests an alternative algorithm for linearization (topological sorting), which repeatedly removes source nodes from the graph (page 101). Show that this algorithm can be implemented in linear time.

Short answer

Answer is not given by the question.

Step-by-step solution

Linearization topology sorting.

Topological sorting

The topological sorting is the traversing of directed acyclic graph in order to get a topological order in a way that the output in decreasing order of post number

Some properties ofTopological sorting are as follows

1). The topological ordering is basically a linear ordering of graph if u and v are the vertices of graph their u must be comes before v.

2). It must be a DAG (directed acyclic graph)

3). The given graph should be directed acyclic graph with no cycle.

4). Every directed acyclic graph must contain at least onetopological ordering.

5). It takes linear time for processing.

Proving the algorithm.

In first step check whether the graph has cycle or not. If not then proceed for topological ordering.in the above graph it does not contain any cycle in it then proceed it to the next step.

Find the degree of the vertices.

Now find out the node with in degree zero and consider it as source vertex.

In degree of any node is the number of edges which directs towards it.

So, here A has in degree zero and B also contain zero as its in degree. Now select anyone from these vertices.

Let A as its source vertex.

Find the cycle and degree.

After selection of A select as its next node because its in degree is zero. And removes source nodes from the graph.

So, after removing both of the vertices, it seems that C has degree 0 and D has 1 in degree. Than select C , up to here the sequence of graph is ABC .

Than eliminate C .now the degree of D and E again zero. Select any one from them. Select D and after that select E. Now the degree of F is zero and the degree of G and H is 1 . After selecting F eliminate F and again look for degree and the degree of both G and H is zero because no other edge is coming on these nodes let select G and after that select H. Similarly apply this method on each and every vertex.

Then the sequence is, ABCDEFGH

Evaluate all possible cases.

Similarly, by selectingas first edge other three case is possible through this they are as follows,

$$\begin{gathered} \mathrm{ABCDEFGH} \\ \mathrm{ABCEDFGH} \\ \mathrm{ABCEDFHG} \\ \mathrm{ABCDEFHG} \end{gathered}$$

Now the next possibility is when the source node as B and after that select A as the next vertex now again find the degree of the each and every node in the graph after eliminating both vertex A and B then it is clear the new degree of C is zero. So, select C . Again D and E are the two option select each of them one by one for showing various possibility.

Then select in one case EFGH .

The other four cases are as follows:

$$\begin{gathered} \mathrm{BACEDFHG} \\ \mathrm{BACDEFHG} \\ \mathrm{BACDEFGH} \\ \mathrm{BACEDFGH} \end{gathered}$$

It takes linear time for processing.And, there are 8 topological orders are possible in the graph.