edited by
5,157 views
29 votes
29 votes

Consider the following directed graph.

Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is $T$, the number of back edges is $B$ and the number of cross edges is $C$. Then

  1. $B = 1$, $C = 1$, and $T = 4$.
  2. $B = 0$, $C = 2$, and $T = 4$.
  3. $B = 2$, $C = 1$, and $T = 3$.
  4. $B = 1$, $C = 2$, and $T = 3$.
  5. $B = 2$, $C = 2$, and $T = 1$.
edited by

2 Answers

Best answer
38 votes
38 votes

Since they said that whenever there is a choice we will have to select the node which is alphabetically earlier, therefore we choose the starting node as $A$.

The tree then becomes  $A-B-E-C$ .  Therefore number of tree edges is $3$, that is, $(T=3)$ .

Now, there is one cycle $B-E-C$, so, we will get a back edge from $C$ to $B$ while performing DFS. Hence $B=1$.

Now, $D$ becomes disconnected node and it can only contribute in forming cross edge . There are $2$ cross edges $D-A$ , $D-B$. Therefore $C=2$.

Answer is Option D.

edited by
11 votes
11 votes

tree edge is an edge in a DFS-tree.

 A back edge connects a vertex to an ancestor in a DFS-tree. Note that a self-loop is a back edge.

cross edge is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other.

Tree edges $\left \{ (a,b),(b,e),(e,c) \right \}$ Cross edges $\left \{ (d,a),(d,b) \right \}$ Back edges $\left \{ (c,b) \right \}$.

edited by
Answer:

Related questions