Virtual Labs

1. Which of the following is a use of the extra ‘visited’ array (the array used to keep track of which nodes have been visited/traversed) in BFS?

a: To avoid getting stuck in a cycle Explanation

Explanation

b: To decide which node to traverse next Explanation

Explanation

c: To preemptively end the algorithm when all nodes are marked as visited thus saving time Explanation

Explanation

d: None of the above Explanation

Explanation

2. What would happen if we used a stack instead of a queue in BFS?

a: The algorithm would simply traverse the graph in the reverse order, i.e, from bottom to top (leaves to root) Explanation

Explanation

b: The algorithm would become equivalent to DFS Explanation

Explanation

c: The algorithm would not work properly, i.e, it will not traverse the graph properly and/or completely Explanation

Explanation

d: No change in the algorithm, i.e, it remains unaffected Explanation

Explanation

3. Why is the time complexity of BFS O(|V| + |E|)?

a: Because it considers all vertices and edges in the worst case Explanation

Explanation

b: Because it considers all vertices and edges in all cases Explanation

Explanation

c: This is not the correct time complexity of BFS Explanation

Explanation

d: None of the above 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 used in BFS to traverse the above graph?

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

Breadth First Search