Difference between revisions of "TADM2E 5.2"

Revision as of 13:03, 3 March 2016

Be sure to apply the errata and change the direction of the edge between F and H.

A topological sorting of this graph would be:

A, B, D, E, C, H, G, I, J, F

--Someguy (talk) 05:13, 3 March 2016 (EST)

After the direction change of the edge between F and H, vertex H has no incoming edges, just like vertex A. If we start DFS at vertex A, according to the "topsort" on page 181, vertex H is supposed to appear at the beginning of the sorting, rather than in the middle:

H, A, B, D, E, C, G, I, J, F

Please correct me if I am wrong.

--Ohk (talk) 08:03, 3 March 2016 (EST)

If the direction from H->F is changed to F->H, then J should be the terminal vertex ?

A pre-order DFS walk should give the ordering : A B C F H G I J D E

The RPO toposort should be : A B D E C F H G I J