Graph Traversal: BFS and DFS Previous Year Questions (PYQs) for GATE DA: 4+ Solved Questions with Step-by-Step Solutions

Consider a directed graph $G=(V,E)$, where $V$ is the finite set of vertices and $E$ is the set of directed edges between the vertices. $G$ may contain cycles but there is no self-loop. Further, $G$ may not be strongly connected.

Let $G^R$ be the graph obtained by reversing the directions of all the edges in $G$ without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex $v$ of a graph visits only the reachable vertices from $v$ in that graph.

Which of the following statements must always be true, regardless of the structure of $G$?

Consider a directed graph $G=(V,E)$, where $V=\{0,1,2,...,100\}$ and $E=\{(i,j):0<j-i\le 2,\text{ for all }i,j\in V\}$. Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex $0$. The number of vertices that will be discovered after vertex $50$ is
(Answer in integer)

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.