Depth first search on graph

Question

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?

Answer 1

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).