Consider the directed acyclic graph G in Figure 1 How many t

Consider the directed acyclic graph G in Figure 1. How many topological orderings does it have? Figure 1 How many topological orderings does this graph have?

Solution

Topological sort pr topological order can be defined as if a path from u to v exist then, u must appear before v. a acyclic graph can have many number of topological orders.

Steps :

1 find indegrees of all vertices.

2. print the vertice with indegree 0.and delete that vertice and update the indegrees of all other vertices.

3. repeat step 1 to 2 until there is no vertex remains.

example :

i am showing one example of the above graph :

b=0

c=1

f=2

e=1

d=1

a=0

print vertex a.

b=0

d=0

c=1

f=2

e=1

print vertex b.

c=0

f=2

e=1

d=0

print vertex d

c=0

f=2

e=0

print vertex c

f=1

e=0

print vertex e

f=0

print vertex f

for this, topological order is a,b,d,c,e,f

here i am replacing a,b,c,d,e,f as 0,1,2,3,4,5 respectively for finding it easily.

All topological sorts are :

******************************END**********************PLS GIVE ME GOOD RATING.....................