GATE CSE 2016 Set 1 | Question: 11

Question

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is _____________.

Comments

Caution: For those who might have this query after going through cormen

One application of DFS is finding Topological sort

But by using DFS you will only get $2$ topological sort$=abcdef,adebcf$

Now between B $\&$ C is there any condition which restricts D coming as per the definition of topological sort $?-NO$

Hence D can come in  b/w B $\&$ C and it will not violate the topological sort. But in DFS this case is not possible.

That's why DFS can give some topological sort but not possible to get all for some graphs.

It's better to approach through brute force.

$a|\_|\_|\_|\_|f$

Now, $b$ must come before $c$ $\&$ $d$ must come before $e$. So, let’s write down all possibilities

$bcde|bdce|bdec\Rightarrow3$

$debc|dbec|dbce\Rightarrow3$

Total $6$ different possibilities.

---

The best method to find Topological Sort w/o any doubt: All Topological Sorts of a Directed Acyclic Graph - GeeksforGeeks

---

for undirected graph what is the answer can anybody tell it

Answer 1

this is according to me I think it is 8 I may be wrong 

Comments

in second last one.. f cannot occur before b and c occur,, hence it is wrong