The GATE Grind

GATE Programming, Data Structures and Algorithms: Graph theory and basic graph algorithms – Previous Year Questions

5 GATE previous year questions on Graph theory and basic graph algorithms (Programming, Data Structures and Algorithms, Data Science and Artificial Intelligence) with answers and explanations, from every paper.

5 questions worth 9 marks in all (1 1-mark, 4 2-mark). Asked between 2024 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2024 DA Q14 (1 mark, Multiple choice) – Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length…
  2. GATE 2024 DA Q51 (2 marks, Multiple select) – Consider the directed acyclic graph (DAG) below: Which of the following is/are valid vertex orderings that can be obtained from a topological sort of…
  3. GATE 2025 DA Q58 (2 marks, Multiple select) – Let G be a simple, unweighted, and undirected graph. A subset of the vertices and edges of G are shown below. It is given that a - b - c - d is a…
  4. GATE 2025 DA Q65 (2 marks, Numerical answer) – Consider a directed graph G = (V, E), where V = \0, 1, 2, , 100\ and E = \(i, j) : 0 < j - i 2, for all i, j V\. Suppose the adjacency list of each…
  5. GATE 2026 DA Q40 (2 marks, Multiple choice) – Consider a directed graph G = (V, E), where V is the finite set of vertices and E is the set of directed edges between the vertices. G may contain…