Topological ordering and DFS

Question

If we apply  Topological and DFS traversal.

Is there any intersection of ordering? Please explain. 

Answer 1

in this particular graph, there is no intersection of topological sort an DFS order.

How?

we all know that if the graph contains a→b and c→b present, in topological order b should be visited after a and c.

in the above graph 1 → 2 and 1 → 4 present, these two individual chains met at 7, i mean 7 should be visited after 2 and 4 visited in any topological sort

coming to DFS starts with 1 ( due to checking for intersection ) either go with 2 or 4 ( either if 2 completely visits then 4 visited or if 4 completely visits then 2 visited )

     i) go with next node 2, 2 → 7, that implies 7 should be visited before going back to 1 ==> 4 should be doesn't visited before 7 visited ===> NO intersection with Topological sort

     ii) go with next node 4, 4 → 7, that implies 7 should be visited before going back to 1 ==> 2 should be doesn't visited before 7 visited ===> NO intersection with Topological sort

Comments

I got this diagram

I got this diagram

if I remove 1, will get two option to choose 2 or 4.........i

Now remove 4 we get again two option 6 or 5..............ii

Now remove 6 , got two option 7 or 3..........................iii

Now remove 7 , we got last 2. option 8 or 9.................iv

thus $2^{4}=16$

---

@Rishav Kumar Singh

after 1->2->3 we can't go to 4  we have to go to 7, so 1->2->3->4 is not possible.WHY??

---

@Shaik Masthan

Topological sort mainly use DFS, not BFS. right??