Q.1 What data structure is primarily used to implement BFS?
Stack
Queue
Priority Queue
Hash Table
Explanation - BFS explores nodes level by level using a queue to maintain the order of traversal.
Correct answer is: Queue
Q.2 What is the time complexity of BFS on a graph with V vertices and E edges?
O(V)
O(E)
O(V+E)
O(V*E)
Explanation - BFS visits each vertex and edge once, giving a time complexity of O(V+E).
Correct answer is: O(V+E)
Q.3 Which traversal technique does BFS resemble in a tree?
Preorder
Inorder
Postorder
Level Order
Explanation - BFS explores nodes level by level, similar to level order traversal in trees.
Correct answer is: Level Order
Q.4 BFS is most suitable for finding what in an unweighted graph?
Shortest Path
Minimum Spanning Tree
Topological Order
Strongly Connected Components
Explanation - BFS guarantees the shortest path in terms of number of edges in an unweighted graph.
Correct answer is: Shortest Path
Q.5 Which of the following is NOT a property of BFS?
Visits nodes level by level
Uses queue
Finds shortest path in weighted graphs
Runs in O(V+E) time
Explanation - BFS finds shortest paths only in unweighted graphs, not weighted ones.
Correct answer is: Finds shortest path in weighted graphs
Q.6 In BFS, when a node is visited, its neighbors are:
Pushed into stack
Inserted into queue
Ignored
Sorted and then visited
Explanation - BFS inserts all unvisited neighbors of a node into the queue for future exploration.
Correct answer is: Inserted into queue
Q.7 BFS can be used to detect what in an undirected graph?
Cycle
Topological order
Minimum spanning tree
Strongly connected components
Explanation - By checking visited neighbors, BFS can detect cycles in undirected graphs.
Correct answer is: Cycle
Q.8 What is the space complexity of BFS?
O(V)
O(E)
O(V+E)
O(V^2)
Explanation - BFS requires space to store visited nodes and the queue, proportional to the number of vertices.
Correct answer is: O(V)
Q.9 If a graph is represented using an adjacency matrix, the time complexity of BFS is:
O(V^2)
O(V+E)
O(E log V)
O(V)
Explanation - Using an adjacency matrix requires scanning all vertices for each node, leading to O(V^2).
Correct answer is: O(V^2)
Q.10 Which problem cannot be solved using BFS?
Shortest path in unweighted graph
Cycle detection
Topological sorting
Connected components
Explanation - Topological sorting requires DFS, not BFS.
Correct answer is: Topological sorting
Q.11 BFS traversal of a disconnected graph requires:
One BFS run
DFS traversal
Multiple BFS runs
Minimum spanning tree
Explanation - Each disconnected component must be traversed separately using BFS.
Correct answer is: Multiple BFS runs
Q.12 Which of the following is an application of BFS?
Finding articulation points
Finding shortest path in unweighted graph
Topological sorting
Finding strongly connected components
Explanation - BFS is mainly used to find shortest paths in unweighted graphs.
Correct answer is: Finding shortest path in unweighted graph
Q.13 In BFS, when is a vertex marked as visited?
When discovered and enqueued
When dequeued
When all neighbors are processed
At the end of traversal
Explanation - BFS marks nodes as visited upon discovery to prevent duplicates in the queue.
Correct answer is: When discovered and enqueued
Q.14 Which type of graph traversal is BFS?
Depth-wise
Level-wise
Random
Priority-based
Explanation - BFS explores all nodes at the same depth before moving to the next level.
Correct answer is: Level-wise
Q.15 If a graph has V vertices and is fully connected, BFS will visit how many vertices?
V-1
V
E
Depends on edges
Explanation - BFS visits all vertices reachable from the source; in a fully connected graph, all V nodes are visited.
Correct answer is: V
Q.16 Which scenario does BFS fail to handle efficiently?
Unweighted shortest path
Weighted shortest path
Cycle detection
Level order traversal
Explanation - BFS assumes equal weights; it cannot compute shortest paths for weighted graphs.
Correct answer is: Weighted shortest path
Q.17 BFS traversal order depends on:
Queue implementation
Adjacency representation order
DFS order
Random selection
Explanation - The order of adjacency list or matrix affects the order of BFS traversal.
Correct answer is: Adjacency representation order
Q.18 Which algorithm is similar to BFS when applied to weighted graphs with equal edge weights?
Dijkstra’s algorithm
Prim’s algorithm
Kruskal’s algorithm
Bellman-Ford
Explanation - BFS and Dijkstra behave the same when all edge weights are equal.
Correct answer is: Dijkstra’s algorithm
Q.19 Which graph representation is most efficient for BFS?
Adjacency List
Adjacency Matrix
Incidence Matrix
Edge List
Explanation - Adjacency list allows BFS to run in O(V+E), making it efficient.
Correct answer is: Adjacency List
Q.20 BFS is considered a __________ algorithm.
Greedy
Divide and Conquer
Brute Force
Uninformed Search
Explanation - BFS explores all possibilities level by level without heuristic guidance.
Correct answer is: Uninformed Search
Q.21 Which problem can be solved using BFS on grids?
Counting connected components
Finding Euler path
Finding Hamiltonian cycle
Graph coloring
Explanation - BFS helps explore connected areas in grid-based problems.
Correct answer is: Counting connected components
Q.22 BFS is an example of which traversal in Artificial Intelligence?
Best-first search
Breadth-first search
Depth-first search
Hill climbing
Explanation - BFS is a uniform and systematic traversal method in AI search trees.
Correct answer is: Breadth-first search
Q.23 What is the main drawback of BFS compared to DFS?
BFS may use more memory
BFS may miss nodes
BFS is slower than DFS always
BFS cannot handle disconnected graphs
Explanation - BFS stores all frontier nodes in memory, which can be large compared to DFS.
Correct answer is: BFS may use more memory
Q.24 If BFS is applied to a binary tree, it results in:
Inorder traversal
Preorder traversal
Postorder traversal
Level order traversal
Explanation - BFS on trees produces level-order traversal.
Correct answer is: Level order traversal
Q.25 Which is TRUE about BFS?
It is recursive
It uses a queue
It requires sorting
It guarantees weighted shortest path
Explanation - BFS is iterative and uses a queue for exploration.
Correct answer is: It uses a queue