Data Structures and Algorithms MCQ - Graph Algorithm

11 Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units,f(P) = 12 units
d(Q) = 6 units,f(Q) = 10 units
d(R) = 14 unit,f(R) = 18 units
which one of the following statements is TRUE about the graph

Since d(q) = d(p) + 1 and F(q) < f(P) which means p & q are connected and r is sperate so option (d) is correct answer.

12 A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph?

Suppose v is starting vertex so start DFS at node v
(i) visit t (v) → DFS(A) → visit (A) → DFS (v) → visit (u) → back track (A) → Back track (v)
therefore d[v] > d[v], d[v] < f[v] f[v] < f[v]
But visiting order is just opposite of finishing order.
Hence f[v] > f[v]

13 Consider the following sequence of nodes for the undirected graph given below:

1. a b e f d g c
2. a b e f c g d
3. a d g e b c f
4. a d b c g e f
A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

a b e f d g c, a b e f c g d, a d g e b c f are possible dFs traverse of given graph.

14 Let G of be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbour s in an adjacency matrix r equires O(V) time, so overall the running time will be O(V²).

15 Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is.

Maximum DFS recurside depth is 19
A → B → C → D → E → F → G → H → I → J → K
→ L → M → N → O → P → Q → R → S

Status
Q	M	N	O	P	R
2	1	1		1
2	2	1		1	1
2	2	2	1	1	1