GATE CSE Graphs & Graph Algorithms – Data Structures Practice Test

Question 71

MSQ · Multiple Correct 2 mark

Which of the following statements regarding Graph Traversals (BFS and DFS) are CORRECT?

A BFS computes unweighted shortest path distances from the source. B DFS uses a stack data structure (either explicitly or via call stack). C BFS on an undirected graph produces tree edges and cross edges only. D DFS can be used to detect cycles in both directed and undirected graphs.

Question 72

MSQ · Multiple Correct 2 mark

Which of the following algorithms can be used to find a Minimum Spanning Tree (MST) of a connected weighted undirected graph?

A Kruskal's Algorithm B Prim's Algorithm C Boruvka's Algorithm D Dijkstra's Algorithm

Question 73

MSQ · Multiple Correct 2 mark

Which of the following conditions are TRUE for a simple undirected graph $G = (V$, E) to be a Tree?

A G is connected and contains no cycles. B G is connected and has exactly V - 1 edges. C G is acyclic and has exactly V - 1 edges. D There is a unique simple path between every pair of vertices in G.

Question 74

MSQ · Multiple Correct 2 mark

Which of the following statements regarding Shortest Path Algorithms are CORRECT?

A Dijkstra's algorithm may fail on graphs with negative edge weights. B Bellman-Ford algorithm can detect negative weight cycles reachable from the source. C Floyd-Warshall computes all-pairs shortest paths using dynamic programming in O($V^3)$ time. D Dijkstra's algorithm always works correctly on graphs with negative cycles.

Question 75

MSQ · Multiple Correct 2 mark

Which of the following are valid Topological Sort sequences for a DAG?

A An ordering where for every directed edge u -> v, u comes before v. B There can be multiple valid topological orderings for a single DAG. C Topological sorting is strictly defined only for Directed Acyclic Graphs. D Every cyclic graph has at least one valid topological sorting.