Graph Traversal: BFS and DFS for Competitive Exams

Graph Traversal: BFS and DFS - Complexity Analysis - Advanced Concepts

Q. In Depth-First Search (DFS), which data structure is primarily used to keep track of the vertices to be explored?

Solution

DFS uses a stack (either explicitly or via recursion) to keep track of the vertices.

Correct Answer: B — Stack

Q. What is the primary disadvantage of using DFS compared to BFS?

Solution

DFS can get stuck in deep paths, potentially missing shorter paths that BFS would find.

Correct Answer: B — Can get stuck in deep paths

Q. What is the time complexity of Breadth-First Search (BFS) in a graph with V vertices and E edges?

Solution

BFS explores all vertices and edges, leading to a time complexity of O(V + E).

Correct Answer: A — O(V + E)

Q. What is the worst-case time complexity for searching an element in a binary search tree (BST) using DFS?

Solution

In the worst case, a BST can degenerate into a linked list, leading to a time complexity of O(V).

Correct Answer: B — O(V)

Q. Which of the following statements is true regarding the time complexity of DFS?

Solution

The time complexity of DFS is O(V + E) as it visits each vertex and edge once.

Correct Answer: A — O(V + E)

Q. Which traversal method can be implemented using recursion?

Solution

DFS can be easily implemented using recursion, while BFS typically requires an iterative approach.

Correct Answer: B — DFS

Q. Which traversal method, BFS or DFS, is more memory efficient in a sparse graph?

Solution

DFS is generally more memory efficient in sparse graphs as it can explore deeper paths without storing all neighbors.

Correct Answer: B — DFS

Showing 1 to 7 of 7 (1 Pages)