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

Thanks @shaik brother

---

@Rishav

if u want intersection between DFS traversal and topological sort

then here every node is in intersection

---

Yes ma'am but in question they are asking about ordering.

Is there any intersection of ordering? 

---

here topological order is 1-2-3-4-5-6-7-8-9

dfs order is 1-2-3-4-5-6-7-8-9

intersection of both is 1-2-3-4-5-6-7-8-9

---

Yes correct, but i think this can't be possible with this graph that both have same ordering

---

here topological order is 1-2-3-4-5-6-7-8-9 is possible BUT

dfs order is 1-2-3-4-5-6-7-8-9 can't be possible.

Correct me ?

---

why?

---

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

---

yes

DFS will be 1-2-3-7-8-4-5-9-6 which is not possible in topological sort

---

Ma'am how many total topological ordering possible on this graph?
I tried but it's very complex for big graphs. Is there any shortcut?

---

will be 16

After 1 there will be two path 2 and 4

fro 4 there will be again 2 path 5 and 6

and also 7. cannot occur before 2 and 8 cannot occur before 5

---

I didn't get, how you got 16. Please explain

---

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??