Skip to content
GATEiit

GATE DA 2024 Q14: Edge type in DFS when explored from nearer vertex

Question

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

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: DFS edge classification in undirected graphs: every edge is a tree edge or a back edge.

First step: If vv were already visited when (u,v)(u,v) is first explored from uu, the edge would have been explored earlier from vv; so vv is undiscovered and the edge becomes a tree edge.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 DA question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key