The GATE Grind

GATE Algorithms: Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths – Previous Year Questions

60 GATE previous year questions on Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths (Algorithms, Computer Science) with answers and explanations, from every paper.

60 questions worth 103 marks in all (17 1-mark, 43 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q5 (1 mark, Multiple choice) – For the shown DAG with V=1, 2, 3, 4, 5, 6, which is NOT a topological ordering?
  2. GATE 2007 CS Q41 (2 marks, Multiple choice) – In an unweighted connected undirected graph, what most efficiently computes shortest paths from S to all other nodes?
  3. GATE 2007 CS Q49 (2 marks, Multiple choice) – In a connected undirected graph, w is the minimum edge weight and e is a specific edge of weight w. Which statement is FALSE?
  4. GATE 2008 CS Q7 (1 mark, Multiple choice) – What is the complexity of the most efficient algorithm to count connected components of an undirected graph with n vertices and m edges?
  5. GATE 2008 CS Q19 (1 mark, Multiple choice) – BFS uses a queue. Which is a possible vertex visitation order for the shown graph?
  6. GATE 2008 CS Q45 (2 marks, Multiple choice) – Run Dijkstra’s single-source shortest-path algorithm from a in the shown directed graph. For which vertices does it compute correct shortest…
  7. GATE 2009 CS Q13 (1 mark, Multiple choice) – Which statements are correct regarding the Bellman–Ford shortest-path algorithm? P. Always finds a negative-weighted cycle, if one exists. Q. Finds…
  8. GATE 2009 CS Q38 (2 marks, Multiple choice) – For the graph shown, which is NOT a possible sequence of edges added by Kruskal’s minimum-spanning-tree algorithm?
  9. GATE 2021 CS (CS2) Q11 (1 mark, Multiple choice) – G is connected, undirected and weighted. S1: Some minimum-weight edge of G is present in every MST. S2: If all edge weights are distinct, G has a…
  10. GATE 2021 CS (CS2) Q56 (2 marks, Multiple select) – For the directed graph shown, which statements hold?
  11. GATE 2021 CS (CS2) Q65 (2 marks, Numerical answer) – In the DAG shown with source s, a path’s quality is the product of its edge weights. A vertex’s quality is the maximum path quality from s;…
  12. GATE 2015 CS (CS3) Q55 (2 marks, Numerical answer) – A connected undirected graph has 100 vertices and 300 edges. Its minimum spanning-tree weight is 500. Every edge weight is increased by five. Find the…
  13. GATE 2015 CS (CS2) Q47 (2 marks, Multiple choice) – Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3 binary search, 4 backtracking graph search, with paradigms i…
  14. GATE 2010 CS Q60 (2 marks, Multiple choice) – The undirected graph on vertices 0,…,4 has weight matrix W=pmatrix0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0pmatrix. Find the minimum…
  15. GATE 2010 CS Q61 (2 marks, Multiple choice) – The undirected graph on vertices 0,…,4 has weight matrix W=pmatrix0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0pmatrix. Find the shortest…
  16. GATE 2011 CS Q64 (2 marks, Multiple choice) – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2; edge weight is i+j. The drawing shows n=4. Find MST cost for…
  17. GATE 2011 CS Q65 (2 marks, Multiple choice) – An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0< i−j ≤2; edge weight is i+j. The drawing shows n=4. For n=10, find…
  18. GATE 2013 CS Q29 (1 mark, Multiple choice) – What is Bellman–Ford’s running time on a complete graph with n vertices?
  19. GATE 2012 CS Q39 (2 marks, MTA) – A graph G has edge weights greater than one. G′ squares every edge weight. T,T′ are minimum spanning trees with weights t,t′. Which is true?
  20. GATE 2012 CS Q50 (2 marks, Multiple choice) – For the shown directed weighted graph, several S-to-T shortest paths exist. Dijkstra updates a vertex’s predecessor only on finding a strictly shorter…
  21. GATE 2017 CS (CS2) Q25 (1 mark, Multiple choice) – BFS is implemented using a queue. Which is a possible vertex-visiting order for the shown graph?
  22. GATE 2014 CS (CS3) Q23 (1 mark, Numerical answer) – Depth-first search starts at an unknown vertex of the graph shown. A recursive visit is made only after checking that the vertex has not been visited.…
  23. GATE 2014 CS (CS3) Q48 (2 marks, Multiple choice) – 2CNFSAT consists of satisfiable propositional CNF formulas with at most two literals per clause; for example (x 1 x 2)(x 1x 3)(x 2 x 4). The decision…
  24. GATE 2014 CS (CS2) Q24 (1 mark, Multiple choice) – A BFS from W in an unweighted connected undirected graph gives tree T. T is a data structure for computing .
  25. GATE 2014 CS (CS2) Q62 (2 marks, Numerical answer) – Find the number of distinct minimum spanning trees of the weighted graph shown.
  26. GATE 2014 CS (CS1) Q13 (1 mark, Multiple choice) – Let G = (V,E) be a directed graph. Which graph has the same strongly connected components as G?
  27. GATE 2014 CS (CS1) Q21 (1 mark, Multiple choice) – G has n vertices and m edges and is represented by an adjacency matrix. Find the tightest upper bound on Depth First Search running time.
  28. GATE 2014 CS (CS1) Q23 (1 mark, Multiple choice) – For the directed graph shown, which statement is TRUE?
  29. GATE 2017 CS (CS1) Q36 (2 marks, Multiple choice) – Let G = (V, E) be *any* connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following…
  30. GATE 2016 CS (CS1) Q21 (1 mark, Numerical answer) – Consider the following directed graph: [Directed graph on vertices a, b, c, d, e, f with edges a→b, b→c, c→f, a→d, d→e, e→f.] The number of different…
  31. GATE 2016 CS (CS1) Q24 (1 mark, Multiple choice) – Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of…
  32. GATE 2016 CS (CS1) Q48 (2 marks, Numerical answer) – Consider the weighted undirected graph with 4 vertices, where the weight of edge \i, j\ is given by the entry W ij in the matrix W. W = bmatrix 0 & 2…
  33. GATE 2016 CS (CS1) Q49 (2 marks, Numerical answer) – Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum…
  34. GATE 2016 CS (CS1) Q50 (2 marks, Multiple choice) – G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements…
  35. GATE 2015 CS (CS1) Q51 (2 marks, Multiple choice) – Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x V, let d(x) denote the shortest distance in G…
  36. GATE 2015 CS (CS1) Q63 (2 marks, Numerical answer) – The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: \(A, C),…
  37. GATE 2018 CS Q40 (2 marks, Multiple choice) – Let G be a simple undirected graph. Let T D be a depth first search tree of G. Let T B be a breadth first search tree of G. Consider the following…
  38. GATE 2018 CS Q57 (2 marks, Numerical answer) – Consider the following undirected graph G (the edge weights are shown in the figure, with one edge of unknown weight x): Choose a value for x that…
  39. GATE 2019 CS Q48 (2 marks, Multiple choice) – Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a…
  40. GATE 2026 CS (CS2) Q37 (2 marks, Multiple choice) – Let G be a weighted directed acyclic graph with m edges and n vertices. Given G and a source vertex s, which one of the following options gives the…
  41. GATE 2026 CS (CS1) Q41 (2 marks, Multiple choice) – Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The…
  42. GATE 2026 CS (CS1) Q49 (2 marks, Multiple select) – Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees…
  43. GATE 2026 CS (CS1) Q50 (2 marks, Multiple select) – Consider the standard depth-first search (DFS) algorithm which takes a directed acyclic graph (DAG) G(V, E) as input, where d[v] and f[v] are the…
  44. GATE 2025 CS (CS2) Q29 (1 mark, Multiple select) – Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
  45. GATE 2025 CS (CS2) Q37 (2 marks, Multiple choice) – Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant is added to the weight of every edge. Which ONE of…
  46. GATE 2025 CS (CS2) Q59 (2 marks, Numerical answer) – Consider the following algorithm someAlgo that takes an undirected graph G as input. someAlgo(G) 1. Let v be any vertex in G. Run BFS on G starting at…
  47. GATE 2025 CS (CS1) Q18 (1 mark, Multiple choice) – Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d 1(u,v) and d…
  48. GATE 2025 CS (CS1) Q43 (2 marks, Multiple choice) – Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v…
  49. GATE 2025 CS (CS1) Q64 (2 marks, Numerical answer) – The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is . (answer in…
  50. GATE 2024 CS (CS2) Q59 (2 marks, Numerical answer) – The number of distinct minimum-weight spanning trees of the following graph is (Vertices a,b,c,d,e,f,g; edges: a-b 1, a-f 1, c-d 1, d-e 1, a-g 2, b-g…
  51. GATE 2024 CS (CS1) Q45 (2 marks, Multiple select) – Let G be a directed graph and T a depth first search (DFS) spanning tree in G rooted at a vertex v. Suppose T is also a breadth first search (BFS)…
  52. GATE 2024 CS (CS1) Q60 (2 marks, Numerical answer) – The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected…
  53. GATE 2023 CS Q56 (2 marks, Numerical answer) – Let U = \1, 2, 3\. Let 2U denote the powerset of U. Consider an undirected graph G whose vertex set is 2U. For any A, B 2U, (A, B) is an edge in G if…
  54. GATE 2022 CS Q49 (2 marks, Multiple select) – Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning…
  55. GATE 2021 CS (CS1) Q27 (1 mark, Numerical answer) – Consider the following undirected graph (a 3x3 grid of vertices, 12 edges) with edge weights: top row horizontal edges 0.1, 0.1; second row horizontal…
  56. GATE 2021 CS (CS1) Q46 (2 marks, Multiple choice) – Let G=(V,E) be an undirected unweighted connected graph. The diameter of G is defined as diam(G)= u,v V\length of shortest path between u and v\. Let…
  57. GATE 2021 CS (CS1) Q51 (2 marks, Multiple select) – An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more…
  58. GATE 2020 CS Q41 (2 marks, Multiple choice) – Let G=(V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted…
  59. GATE 2020 CS Q50 (2 marks, Multiple choice) – Let G=(V,E) be a directed, weighted graph with weight function w:ER. For some function f:VR, for each edge (u,v) E, define w'(u,v) as…
  60. GATE 2020 CS Q59 (2 marks, Numerical answer) – Consider a graph G=(V,E), where V=\v 1,v 2,,v 100\, E=\(v i,v j) 1 i<j 100\, and weight of the edge (v i,v j) is i-j . The weight of minimum spanning…