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

Question

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.

Answer 1

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.

Answer 2

If your graph is strongly connected, there is no sink, so I guess that answers your question...

Answer 3

See this graph, d = pre-order, f = postorder. Vertex 4 is not a sink. For more http://www.cs.usfca.edu/~galles/visualization/ConnectedComponent.html