GATE DS&AI 2024 | Question: 4

Question

​​​​Consider performing depth-first search (DFS) on an undirected and unweighted graph $G$ starting at vertex $s$. For any vertex $u$ in $G, d[u]$ is the length of the shortest path from $s$ to $u$. Let $(u, v)$ be an edge in $G$ such that $d[u]<d[v]$. If the edge $(u, v)$ is explored first in the direction from $u$ to $v$ during the above DFS, then $(u, v)$ becomes a $\_\_\_\_\_\_\_\_$ edge.

• A. tree
• B. cross
• C. back
• D. gray

Answer 1

A