1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Please give definitions of pre- and postorder and state, whether you are interested in the degree in the graph itself or the resulting search tree. $\endgroup$
    – frafl
    Jun 9 '13 at 14:13
  • $\begingroup$ Usually the standard way to answer questions like these on you rown is to try some small examples, and you will probably quickly discover a solution for yourself.... $\endgroup$
    – D.W.
    Sep 22 '13 at 6:31
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.