The GATE Grind

GATE 2024 DA – Question 14

Programming, Data Structures and Algorithms · Graph theory and basic graph algorithms · 1 mark · Multiple choice

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.

  1. tree
  2. cross
  3. back
  4. gray

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) tree

Explanation

When an edge is explored from $u$ to a vertex $v$ that has not been visited yet, it becomes a tree edge. Because $d[v] > d[u]$ and the edge is first explored from $u$, $v$ is discovered through this edge. (In an undirected graph there are no cross edges, and a back edge goes to an ancestor that is already visited.)