GATE CS 2003 Q21 — Graph Traversals (BFS, DFS)

The given graph has the vertex set $V = \{a, b, e, f, g, h\}$ with the following edge connections:

• $a$ is connected to $b, f$
• $b$ is connected to $a, e, f, h$
• $e$ is connected to $b, g$
• $f$ is connected to $a, b, g, h$
• $g$ is connected to $e, f, h$
• $h$ is connected to $b, f, g$

Let's analyze each sequence using Depth-First Search (DFS) rules:

1. I. $a \to b \to e \to g \to h \to f$: Valid. From $a$, we visit $b$, then $e$, then $g$, then $h$, and finally $f$. All steps follow valid unvisited adjacent edges.
2. II. $a \to b \to f \to e \to h \to g$: Invalid. After visiting $f$, we backtrack to $b$ to visit $e$. From $e$, the only unvisited neighbor is $g$. In DFS, we must explore the unvisited neighbor $g$ before backtracking. Thus, we cannot jump to $h$ from $e$ or backtrack to $b$ to reach $h$ while $g$ remains unvisited.
3. III. $a \to b \to f \to h \to g \to e$: Valid. From $a \to b \to f \to h \to g$, the only unvisited vertex left is $e$, which is directly connected to the current vertex $g$.
4. IV. $a \to f \to g \to h \to b \to e$: Valid. From $a \to f \to g \to h \to b$, the only unvisited vertex left is $e$, which is directly connected to the current vertex $b$.

Thus, sequences I, III, and IV are valid depth-first traversals.