Graph Algorithms (DFS, BFS, Dijkstras, etc) MCQ question and answer with solution | Data Structure MCQs

A. BFS does not guarantee the shortest path.

B. BFS always finds the shortest path in an unweighted graph.

C. BFS requires a sorted graph.

D. BFS does not guarantee the shortest path.

A. Directed and undirected graphs

B. Only undirected graphs

C. Only directed graphs

D. Only weighted graphs

A. O(V log V)

B. O(E log V)

C. O(V²)

D. O(V + E)

A. Prim's Algorithm

B. Depth-First Search (DFS)

C. Dijkstra's Algorithm

D. Kruskal's Algorithm

A. When the graph is sparse.

B. When you need the shortest path between all pairs of nodes.

C. When the graph is directed only.

D. When the graph is sparse.

A. An edge that causes a cycle in the graph.

B. An edge that connects two nodes in the same level.

C. An edge that connects a node to its ancestor in the DFS tree.

D. An edge that connects a node to a descendant in the DFS tree.

A. It ignores them.

B. It transforms negative weights into positive weights.

C. It cannot handle them.

D. It can handle them and detect negative weight cycles.

A. Adjacency list

B. Adjacency matrix

C. Both are equally efficient.

D. It depends on the graph density.

A. Depth-First Search (DFS)

B. BFS

C. Dijkstra's Algorithm

D. Dynamic Programming

A. All nodes are red.

B. The tree is always perfectly balanced.

C. Every path from the root to a leaf has the same number of black nodes.

D. Nodes can only have two children.