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.

Improve this question
$\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
    Commented Jun 9, 2013 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. ♦
    Commented Sep 22, 2013 at 6:31

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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