GATE PYQ

Algorithm

Q71.
Which of the following is application of Breath First Search on the graph?

Q72.
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

Q73.
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

Q74.
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .

Q75.
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 of the above is/are possible output(s)?

Q76.
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 _________.

Q77.
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

Q78.
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is

Q79.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1. Which of the statements above must necessarily be true?

Q80.
In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is