BFS-and-DFS

Question 1

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
Data-StructuresBFS-and-DFSGATE 2017 [Set-2]Video-Explanation
Question 1 Explanation: 
The possible order of visiting the nodes in Breadth First Search Algorithm, implementing using Queue Data Structure is

(Do it by option Elimination)
(a) MNOPQR – MNO is not the proper order R must come in between.
(b) NQMPOR – QMP is not the order O is the child of N.
(C) QMNROP – M is not the child of Q, so QMN is false.
(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).
Question 2

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
31
B
32
C
33
D
34
Data-StructuresBFS-and-DFSGATE 2016 [Set-2]Video-Explanation
Question 2 Explanation: 
Given is a vertex t at a distance of 4 from the root.

For distance 1, max possible value is (3).
Similarly, for distance 2, max value is (7).
So, maximum number of nodes = 2(h+1) - 1
For distance 4, 2(4+1) - 1 ⇒ 25 - 1 ⇒ 32 - 1 = 31
31 is the last node.

So for distance 4, the maximum possible node will be 31 & minimum will be 16.
Question 3
Let U = {1, 2, 3}. Let 2U denote the powerset of U. Consider an undirected graph G whose vertex set is 2U . For any A, B ε 2U , (A, B) is an edge in G if and only if

For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A). If ∅ denotes the empty set, then the cardinality of B(∅) is ______?
A
5040
Data-StructuresBFS-and-DFSGATE 2023Video-Explanation
Question 4

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source.  For x ∈ 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
Engineering-MathematicsBFS-and-DFSGATE 2015 [Set-1]Video-Explanation
Question 4 Explanation: 
In an undirected graph if (u, v) be the edge then (u, v) also the edge. So shortest path that can be obtained by the (u, v) of (u, v).
Then the difference between the d(u) and d(v) is not more than '1'.
In the option 'D' the difference is given as '2' it is not possible in the undirected graph.
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access