Breadth First Search

1. Which of the following are applications of BFS?

a: Constructing a spanning tree of an unweighted graph Explanation

Explanation

b: Finding shortest distances from a source in an unweighted graph Explanation

Explanation

c: Detecting cycles in an undirected graph Explanation

Explanation

d: All of the above Explanation

Explanation

2. Imagine a

4 \times 4

grid (assume 1-based indexing) where the hero stands in cell

(2,3)

and the villain is in cell

(3,1)

. Assuming the hero can move only up, down, left, or right to an immediately adjacent cell and cannot move outside the grid, how many steps will it take for the hero to reach the stationary villain?

a: 1 Explanation

Explanation

b: 2 Explanation

Explanation

c: 3 Explanation

Explanation

d: 4 Explanation

Explanation

3. In BFS, why is a vertex marked as visited when it is first discovered?

a: To ensure that the vertex is never processed Explanation

Explanation

b: To prevent the vertex from being added to the queue multiple times Explanation

Explanation

c: To force BFS to process the vertex before its parent Explanation

Explanation

d: To sort the vertices according to their labels Explanation

Explanation

4. What is the main difference between BFS and DFS in terms of the data structure used to manage the next vertex to process?

a: BFS uses a queue, while DFS typically uses a stack Explanation

Explanation

b: BFS uses a stack, while DFS uses a queue Explanation

Explanation

c: Both always use a heap Explanation

Explanation

d: Neither requires an auxiliary data structure Explanation

Explanation

5. Consider an unweighted graph. BFS starts at vertex

s

and first reaches vertex

v

after traversing 4 edges. What can be concluded?

a: The shortest distance from

s

v

is 4 Explanation

Explanation

b: Every path from

s

v

contains exactly 4 edges Explanation

Explanation

c: The graph contains exactly 4 vertices Explanation

Explanation

d: DFS would necessarily reach

v

in 4 edges Explanation

Explanation

6. Which statement about BFS on a disconnected graph is correct?

a: A single BFS starting from one vertex always visits every vertex Explanation

Explanation

b: BFS cannot be used on a disconnected graph Explanation

Explanation

c: A single BFS visits only the vertices reachable from its starting vertex Explanation

Explanation

d: BFS automatically joins all disconnected components Explanation

Explanation

7. In an unweighted graph, BFS is commonly preferred over DFS when the goal is to find the shortest path from a source to a target because BFS:

a: always visits vertices alphabetically Explanation

Explanation

b: always examines fewer edges than DFS Explanation

Explanation

c: uses no additional memory Explanation

Explanation

d: explores vertices in nondecreasing order of their distance from the source Explanation

Explanation

8. Suppose BFS is performed on a graph using an adjacency list. Which operation contributes to the

O(|V| + |E|)

time complexity?

a: Sorting all vertices before traversal Explanation

Explanation

b: Examining the adjacency list of each visited vertex Explanation

Explanation

c: Comparing every vertex with every other vertex Explanation

Explanation

d: Rebuilding the entire graph after processing each vertex Explanation

Explanation

9. Consider an undirected graph with source vertex

s

. During BFS, vertex

x

is discovered from vertex

y

. If the BFS distance of

y

from

s

k

, what distance is assigned to

x

when

x

is first discovered?

k

Explanation

k - 1

Explanation

k + 1

Explanation

2k

Explanation