Graphs, Traversals and Shortest Paths - Programming, Data Structures and Algorithms - Data Science & Artificial Intelligence Previous Year Questions

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.

Consider the following tree traversals on a full binary tree:
(i) Preorder
(ii) Inorder
(iii) Postorder
Which of the following traversal options is/are sufficient to uniquely reconstruct the full binary tree?

Consider the directed acyclic graph (DAG) below:
Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

Let \(G\) be a simple, unweighted, and undirected graph. A subset of the vertices and edges of \(G\) are shown below.
[Image]
It is given that \(a - b - c - d\) is a shortest path between \(a\) and \(d\); \(e - f - g - h\) is a shortest path between \(e\) and \(h\); \(a - f - c - h\) is a shortest path between \(a\) and \(h\). Which of the following is/are NOT the edges of \(G\)?

Consider a directed graph \(G = (V, E)\), where \(V = \{0, 1, 2, \dots, 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)

You are given the following Pre-order and In-order traversals of a Binary Tree T with nodes E, F, G, P, Q, R, S.
Pre-order:    P    Q    S    E    R    F    G
In-order:     S    Q    E    P    F    R    G
Which of the following statements is/are true about the Binary Tree T?

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?