depth first search - How can we find the initial node in order to apply the algorithm?

Question

Consider the following graph G and consider that at an execution of the algorithm DFS at G, the edges of the graph are characterized as tree edges(t), back edges(b) , forward edges(f) and cross edges(c) as at the following graph. For each node of the graph find the discovery time and the finishing time of the node. In other words, for each node v of the graph, find the values d[v] and f[v] that associates the algorithm DFS with this node.

Notice that there is only one possible assignment of the values d[v] and f[v].

Could you give me a hint how we can find the initial node in order to start applying the Depth first search algorithm?

Answer 1

Look at node a - what could DFS do in node a? It could go either to b or e. We see that it chose b, because a->b is a tree edge and a->e is a forward edge (check the definition of tree/forward edge). In b the only choice was to visit f. In f DFS could go either to a, e or g. We can assume that it tried to visit a (f->a is marked as back edge, so everything is correct until now), than it visited e and than tried to visit b. However, we now have a problem with edge f->g. It is marked as a cross edge, which means that DFS had already visited g before. Otherwise, this edge would have been marked as a tree edge. So, we know that a was not the initial node. We need to try other options. What about c? Again, all of edges coming out of c are marked as cross, not tree, so c was not the initial node.

What about d? If DFS started in d, it could go from d to g and that's what happened because d->g is marked as tree edge. There were no nodes to go from g so it backtraced to d and visited h. From h it tried to visit g but it has already visited earlier, so h->g is marked as cross - correct. Great, so d was the initial node for this DFS execution. After visiting a connected component which contains d, g and h, DFS could start again either from a or c but we already know that it has not started from c because of those cross edges. So it started from a and after visiting b, f and e it started from c.