GATE DA 2024 — Question 14

Programming, Data Structures and Algorithmsbasic graph algorithms: traversals and shortest pathMCQ1 mark · −1/3 if wrongMedium

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. A
    tree
  2. B
    cross
  3. C
    back
  4. D
    gray
Practise the full 2024 paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on basic graph algorithms: traversals and shortest pathTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group