Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a homework problem I think I know the answer to, but want to double check

Consider the graph with three nodes, $a$, $b$, and $c$, and the two arcs $a \rightarrow b$ and $b \rightarrow c$. Give all the possible depth-first search forests for this graph, considering all possible starting nodes for each tree. What is the postorder numbering of the nodes for each forest? Are the postorder numbers always the same for this graph?

I know what to do for DFS, but I am unsure whether or not there will be multiple trees for this example. I do not see how there could be. If you start at node a, you will immediately go to c, giving (c,b,a). Start at b, you will get the same thing, etc.

Am I thinking of this correctly?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

I assume that the edges are directed, i.e. $A \to B \to C$. Start from:

  • $A$ - $A(B(C))$ - one tree,
  • $B$ - $B(C)$ $A$ - two trees,
  • $C$ and then $B$ - $C$ $B$ $A$ - three trees,
  • $C$ and then $A$ - $C$ $A(B)$ - two trees.

Postorder numbers will be always $A$-3, $B$-2, $C$-1 because $C$ will always go before $B$, and $B$ will always go before $A$, and there are no other vertices to interfere (go in between).

Hope it clarified something :-)

Bonus: The fact that DFS search tree can be a forest is used e.g. in one of the algorithms for strongly connected components:

  • run an arbitrary DFS,
  • reverse the edges' direction,
  • run a second DFS, but starting with vertices according to the postorder of the first DFS (this ensures that the second search forest will be as fragmented as possible),
  • each tree of search forest will be some strongly connected component (because if we weren't able to split it, it must have been strongly connected).
share|improve this answer
    
Yes the graph is undirected. And thanks for the answer. After thinking for a while this is the solution I came up with, just wanted a second opinion. Thanks again! –  MZimmerman6 Dec 2 '12 at 23:19
    
@MZimmerman6 With undirected graph you have always one tree for every connected component. –  dtldarek Dec 2 '12 at 23:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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