[Solved]: Why is the node with the greatest DFS post-order number not necessarily a sink?

Problem Detail: 

A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not necessarily a sink - isn't this node found last?

Also, intuitively, the node with the greatest post-order number should be a source - a node with no incoming edges.

Asked By : David Faux

Answered By : frafl

The earliest finished vertex of a DFS is a leaf (or sink in your language) of the search tree, i.e. a leaf in the original digraph or the last seen vertex of some directed cycle.

The vertex which is finished last (biggest post order number) is the vertex where you started the search and, by construction, a source of the search tree. It may have any number of incoming edges in the original graph.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12559