Breadth First Search

1. Which of the following is a use of the extra 'visited' array in BFS?

a: To avoid repeatedly visiting vertices in a cycle Explanation

Explanation

b: To decide which vertex is at the front of the queue Explanation

Explanation

c: To sort the vertices before traversal Explanation

Explanation

d: To store the edges of the graph Explanation

Explanation

2. What would happen if a stack were used instead of a queue to control the order of vertex processing in a standard graph traversal?

a: The algorithm would simply traverse the graph from bottom to top Explanation

Explanation

b: The traversal would follow DFS-style depth-first behavior Explanation

Explanation

c: The graph could no longer be traversed Explanation

Explanation

d: There would be no change in the traversal order Explanation

Explanation

3. Why is the time complexity of BFS

O(|V| + |E|)

when an adjacency-list representation is used?

a: Because it processes each reachable vertex and examines the relevant edges Explanation

Explanation

b: Because it considers every possible pair of vertices Explanation

Explanation

c: Because BFS always visits every vertex and every edge even in a disconnected component Explanation

Explanation

d: Because BFS repeatedly sorts all vertices and edges Explanation

Explanation

4. 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 and 'a' is the root.
Which of the following represents the correct sequence of the queue during BFS, assuming a vertex is marked visited when it is first added to the queue?

a: [] → [a] → [b, c] → [b, e, f] → [b, e] → [b] → [d] → [] Explanation

Explanation

b: [] → [a] → [a, b, c] → [a, b, c, d, e] → [a, b, c, d, e, f] Explanation

Explanation

c: [] → [a] → [b, c] → [c, d] → [d, e, f] → [e, f] → [f] → [] Explanation

Explanation

d: [] → [a] → [b, c] → [c, d, e] → [d, e, f] → [e, f] → [f] → [] Explanation

Explanation

5. In an unweighted graph, what does the BFS level of a vertex represent relative to the source vertex?

a: The number of vertices in the graph Explanation

Explanation

b: The number of edges in a shortest path from the source to that vertex Explanation

Explanation

c: The number of edges incident to that vertex Explanation

Explanation

d: The position of the vertex in the adjacency list Explanation

Explanation

6. Which of the following best explains why BFS processes a graph level by level?

a: The queue processes vertices in FIFO order Explanation

Explanation

b: The queue processes vertices in LIFO order Explanation

Explanation

c: Vertices are always processed in alphabetical order Explanation

Explanation

d: All vertices are processed simultaneously Explanation

Explanation

7. Suppose a connected graph contains

|V|

vertices. During a BFS traversal starting from one source, each vertex other than the source is assigned exactly one BFS-tree parent. How many edges are present in the resulting BFS tree?

|V|

Explanation

|V| + 1

Explanation

|V| - 1

Explanation

2|V|

Explanation

8. If BFS is started from a vertex in a disconnected graph, what will happen?

a: BFS will automatically create edges between disconnected components Explanation

Explanation

b: BFS will visit every vertex regardless of connectivity Explanation

Explanation

c: BFS will visit only the vertices reachable from the starting vertex Explanation

Explanation

d: BFS will always terminate before visiting the starting vertex Explanation

Explanation

9. Consider two vertices

u

and

v

in an unweighted graph. BFS discovers

u

at level 2 and discovers

v

directly from

u

. Assuming

v

has not been visited before, at which level will

v

be placed?

a: Level 1 Explanation

Explanation

b: Level 2 Explanation

Explanation

c: Level 4 Explanation

Explanation

d: Level 3 Explanation

Explanation