Topological order

Question

Will the topological order for acyclic graph through indegree Elimination method and DFS method be same.

Please answer the above question ?

Comments

@Shaikh..the only topological sorting that I know is this one..I don't think there is some other method...

---

The in-degree elimination method you will find in Rosen under discussion of Hasse diagrams and partial orderings. The DFS method is in Cormen. I too have this confusion on which to use where (atleast for Hasse diagrams it is definitely the former).

In compilers, for eg, one standard book exercise question asks to find the toposort of a SDD dependency graph. If I use the DFS method, I get different results from the in-degree elimination method.

---

Even i dont know shaik masthan.

Answer 1

Take this  graph, in this if we apply topological ordering, then 0 can't come before 4 or 5, BUT if we apply DFS 0 can come before them. What i mean is if we start topological ordering with vertex 5 then one of many order will be, 5,4,0,2,3,1

But if we apply DFS with 5 as start vertex then one of order  may be  5,0,2,3,1,4

So, for this graph they are not same, may be for other graph it will be same.

Comments

Thanku Rishab

---

Good answer.