Q49: DFS in lexical order

Posted on by bytesoftheday

Question #49: For the following graph, let’s assume A is the starting node and we traverse the graph using DFS (Depth First Search) in lexical order. What would be the order of traversal?

graph

Options:

  1. A, B, C, G, D, H, F, E
  2. A, B, C, F, G, D, H, E
  3. A, E, B, C, F, G, D, H
  4. A, E, B, F, D, G, D, H

Solution: A would be followed by B instead of E or F to follow the lexical order. Now, after B would be C. Similarly after C, F would be preferred instead of G and so on. 2nd option is the right answer.