TIFR CSE 2014 | Part B | Question: 3

Question

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

• A. $B = 1$, $C = 1$, and $T = 4$.
• B. $B = 0$, $C = 2$, and $T = 4$.
• C. $B = 2$, $C = 1$, and $T = 3$.
• D. $B = 1$, $C = 2$, and $T = 3$.
• E. $B = 2$, $C = 2$, and $T = 1$.

Comments

the key point before starting think which vertex to start  then

whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen

---

Correct!

---

https://www.youtube.com/watch?v=8jmt6Kxjlwc&t=402s

Answer 1

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.

Comments

@`JEET

It's because the question asked to take the node $a$ as the source as it is assumed by the following line in the question.

the vertex earlier in the alphabetical order

---

how can there be a back edge in the DFS traversal of a graph.

---

@sayan chowdhury take any cyclic graph then write a dfs tree for the graph, you will find back-edge. 

Answer 2

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

A 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 \}$.

Comments

but how can we pick randomly in the middle if there is no directed edge...since we use stack and push the vertices....is it compulsory to visit all the vertex in DFS traversal??

---

Yes in both BFS and DFS  it compulsory to visit all the vertex.

You just have scan array ones to find those vertices which are not visited (just traverse the visited array find the first vertex which is still at 0) then pic that vertex and do DFS again no need to visit those vertex which are already visited.

---

@cse23 Yes. I have the same question. But then I guess as it is mentioned whenever there comes a question of choosing, alphabetical order should be followed. So maybe for choosing the starting vertex also we should follow the same.