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
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.
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
Hi Ohk, thanks for the reply.
The original graph on page 185 in the book pdf (obtained from "sist.sysu.edu.cn/~isslxm/DSA/textbook/Skiena.-.TheAlgorithmDesignManual.pdf") contains a directed cycle (G->F->H->G). According to the errata ("www3.cs.stonybrook.edu/~skiena/algorist/book/errata"), we should "reverse the edge (F,H)" to make it acyclic; that is to say changing the edge from F->H to H->F. It is different from yours (from H->F to F->H).
As I understand, after the change either J or F could be the terminal vertex, since both vertices have no outgoing edges. A and H have no incoming edges, so they are unreachable from other vertices.
I removed the http// prefix in the above links as I do not have the right to put external link.