Follow Us :

Data Structures and Algorithms - Graph Algorithm

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > 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

  • Option : D
  • Explanation :
    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.
Cancel reply
Cancel reply

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?

  • Option : D
  • Explanation :

    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]
Cancel reply
Cancel reply

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)?

  • Option : D
  • Explanation :
    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.
Cancel reply
Cancel reply

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?

  • Option : C
  • Explanation :
    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(V2).
Cancel reply
Cancel reply

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.

  • Option : A
  • Explanation :

    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
Cancel reply
Cancel reply
Related Quiz.
Graph Algorithm