1,284 views

1 Answer

Best answer
2 votes
2 votes
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
selected by

Related questions

2 votes
2 votes
0 answers
1
h4kr asked Jan 10, 2023
337 views
1 votes
1 votes
1 answer
3
kamakshi asked Nov 18, 2017
1,339 views
Caption