Breadth First Search

1. Consider the following graph:
Vertices, V = [a, b, c, d, e, f]
Edges, E = [[a, b], [a, c], [b, d], [b, e], [c, e], [c, f]]
Where each array within E signifies an edge between the two mentioned vertices.
How many queue-deletion iterations are required for BFS to completely traverse this graph when starting from vertex 'a' and marking each vertex as visited when it is first added to the queue?

a: 3 Explanation

Explanation

b: 5 Explanation

Explanation

c: 6 Explanation

Explanation

d: 7 Explanation

Explanation

2. When comparing the auxiliary space requirements of BFS and DFS on a graph, under what condition can BFS require more space than DFS? Here, BFS space is associated with the maximum frontier size and DFS space with the maximum depth of the traversal.

a: When the maximum depth is greater than the maximum frontier size Explanation

Explanation

b: When the maximum frontier size is greater than the maximum depth Explanation

Explanation

c: BFS always uses less space than DFS Explanation

Explanation

d: DFS always uses more space than BFS Explanation

Explanation

3. What is the main reason BFS can be used to find shortest paths in an unweighted graph?

a: BFS explores vertices in increasing order of their distance from the source Explanation

Explanation

b: BFS always selects the vertex with the smallest label Explanation

Explanation

c: BFS sorts all graph edges before traversal Explanation

Explanation

d: BFS visits all vertices at random Explanation

Explanation

4. Which statement correctly describes the role of the queue in BFS?

a: It stores vertices according to their numerical value Explanation

Explanation

b: It ensures that recently discovered vertices are always processed first Explanation

Explanation

c: It ensures that the earliest discovered vertex is processed first Explanation

Explanation

d: It stores only the vertices that have already been completely processed Explanation

Explanation

5. Consider a graph with

|V|

vertices and

|E|

edges represented by adjacency lists. What is the time complexity of BFS when all reachable vertices and their adjacency lists are processed?

O(|V| + |E|)

Explanation

O(|V|^2)

Explanation

O(|E|^2)

Explanation

O(|V| \cdot |E|)

Explanation

6. A BFS implementation marks a vertex as visited only when it is removed from the queue instead of when it is first discovered. What problem can arise in a graph where multiple vertices have edges to the same unvisited vertex?

a: The graph becomes disconnected Explanation

Explanation

b: The queue may contain the same vertex multiple times Explanation

Explanation

c: BFS automatically becomes DFS Explanation

Explanation

d: The number of vertices in the graph changes Explanation

Explanation

7. Consider an unweighted graph in which BFS assigns distance

0

to the source vertex. If vertex

x

receives distance

4

, what does this distance represent?

a: The number of vertices in the graph Explanation

Explanation

b: The number of edges incident on

x

Explanation

c: The number of BFS levels after

x

is processed Explanation

Explanation

d: The number of edges in a shortest path from the source to

x

Explanation

8. In a BFS traversal of a connected graph, a vertex is placed in the queue when it is first discovered. Which statement about that vertex is correct?

a: It must be processed immediately before its parent Explanation

Explanation

b: It will be processed before every vertex discovered at an earlier level Explanation

Explanation

c: It will eventually be removed from the queue and processed unless the traversal is terminated early Explanation

Explanation

d: It can never have an edge to another vertex at the same level Explanation

Explanation

9. Consider an unweighted graph where two different paths from source

s

to vertex

v

contain 3 and 5 edges respectively. If BFS reaches

v

through the path containing 3 edges first, what distance should BFS assign to

v

a: 3 Explanation

Explanation

b: 5 Explanation

Explanation

c: 8 Explanation

Explanation

d: The distance cannot be determined Explanation

Explanation