Graphs MCQ question and answer with solution | Data Structure MCQs

A. Prim's Algorithm

B. Floyd-Warshall Algorithm

C. Bellman-Ford Algorithm

D. Kruskal's Algorithm

A. The graph is bipartite.

B. The graph contains multiple cycles.

C. The shortest path cannot be computed reliably.

D. The graph is a complete graph.

A. O(E)

B. O(V + E)

C. O(V log V)

D. O(E)

A. By applying dynamic programming only once.

B. By performing DFS from each vertex.

C. By considering all pairs of vertices and iteratively updating shortest paths.

D. By using a priority queue for edge relaxation.

A. To store all edges of the graph.

B. To maintain the order of vertices during BFS.

C. To perform depth-first search more efficiently.

D. To efficiently extract the vertex with the minimum distance.

A. Tarjan's Algorithm

B. Kruskal's Algorithm

C. Prim's Algorithm

D. Dijkstra's Algorithm

A. A minimum spanning tree of the graph.

B. A breadth-first search traversal of the graph.

C. A depth-first search traversal of the graph.

D. A linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v.

A. Stack

B. Priority Queue

C. Queue

D. Linked List

A. O(E)

B. O(V + E)

C. O(V log V)

D. O(E)

A. When the graph is bipartite.

B. When the graph has negative weights.

C. When the graph is dense.

D. When the graph is sparse.