Graph Traversal (BFS and DFS)

Question 1
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
A
Root of T can never be an articulation point in G.
B
Root of T is an articulation point in G if and only if it has 2 or more children.
C
A leaf of T can be an articulation point in G.
D
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
GATE CSE 2021 SET-1   Algorithm
Question 2
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
A
v2v4
B
v1v4
C
v4v5
D
v3v4
ISRO CSE 2020   Algorithm
Question 3
Which of the following is application of Breath First Search on the graph?
A
Finding diameter of the graph
B
Finding bipartite graph
C
Both (A) and (B)
D
None of the above
ISRO CSE 2018   Algorithm
Question 4
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?
A
I only
B
II only
C
Both I and II
D
Neither I nor II
GATE CSE 2018   Algorithm
Question 5
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?
A
MNOPQR
B
NQMPOR
C
QMNROP
D
POQNMR
GATE CSE 2017 SET-2   Algorithm
Question 6
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______ .
A
16
B
15
C
31
D
32
GATE CSE 2016 SET-2   Algorithm
Question 7
Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is
A
4
B
5
C
6
D
7
GATE CSE 2016 SET-1   Algorithm
Question 8
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?
A
-1
B
0
C
1
D
2
GATE CSE 2015 SET-1   Algorithm
Question 9
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 _________.
A
16
B
19
C
17
D
20
GATE CSE 2014 SET-3   Algorithm
Question 10
Let G 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?
A
\Theta (n)
B
\Theta (n+m)
C
\Theta (n^{2})
D
\Theta (m^{2})
GATE CSE 2014 SET-1   Algorithm
There are 10 questions to complete.

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.