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.
- GATE 2007 CS Q5 – For the shown DAG with V=1, 2, 3, 4, 5, 6, which is NOT a topological ordering?
- GATE 2007 CS Q41 – In an unweighted connected undirected graph, what most efficiently computes shortest paths from S to all other nodes?
- GATE 2007 CS Q49 – In a connected undirected graph, w is the minimum edge weight and e is a specific edge of weight w. Which statement is FALSE?
- GATE 2008 CS Q7 – What is the complexity of the most efficient algorithm to count connected components of an undirected graph with n vertices and m edges?
- GATE 2008 CS Q19 – BFS uses a queue. Which is a possible vertex visitation order for the shown graph?
- GATE 2008 CS Q45 – Run Dijkstra’s single-source shortest-path algorithm from a in the shown directed graph. For which vertices does it compute correct shortest…
- GATE 2009 CS Q13 – Which statements are correct regarding the Bellman–Ford shortest-path algorithm? P. Always finds a negative-weighted cycle, if one exists. Q. Finds…
- GATE 2009 CS Q38 – For the graph shown, which is NOT a possible sequence of edges added by Kruskal’s minimum-spanning-tree algorithm?
- GATE 2021 CS (CS2) Q11 – 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…
- GATE 2021 CS (CS2) Q56 – For the directed graph shown, which statements hold?
- GATE 2021 CS (CS2) Q65 – 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;…
- GATE 2015 CS (CS3) Q55 – 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…
- GATE 2015 CS (CS2) Q47 – Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3 binary search, 4 backtracking graph search, with paradigms i…
- GATE 2010 CS Q60 – 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…
- GATE 2010 CS Q61 – 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…
- GATE 2011 CS Q64 – 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…
- GATE 2011 CS Q65 – 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…
- GATE 2013 CS Q29 – What is Bellman–Ford’s running time on a complete graph with n vertices?
- GATE 2012 CS Q39 – 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?
- GATE 2012 CS Q50 – 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…
- GATE 2017 CS (CS2) Q25 – BFS is implemented using a queue. Which is a possible vertex-visiting order for the shown graph?
- GATE 2014 CS (CS3) Q23 – 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.…
- GATE 2014 CS (CS3) Q48 – 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…
- GATE 2014 CS (CS2) Q24 – A BFS from W in an unweighted connected undirected graph gives tree T. T is a data structure for computing .
- GATE 2014 CS (CS2) Q62 – Find the number of distinct minimum spanning trees of the weighted graph shown.
- GATE 2014 CS (CS1) Q13 – Let G = (V,E) be a directed graph. Which graph has the same strongly connected components as G?
- GATE 2014 CS (CS1) Q21 – 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.
- GATE 2014 CS (CS1) Q23 – For the directed graph shown, which statement is TRUE?
- GATE 2017 CS (CS1) Q36 – 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…
- GATE 2016 CS (CS1) Q21 – 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…
- GATE 2016 CS (CS1) Q24 – 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…
- GATE 2016 CS (CS1) Q48 – 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…
- GATE 2016 CS (CS1) Q49 – 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…
- GATE 2016 CS (CS1) Q50 – 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…
- GATE 2015 CS (CS1) Q51 – 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…
- GATE 2015 CS (CS1) Q63 – 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),…
- GATE 2018 CS Q40 – 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…
- GATE 2018 CS Q57 – 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…
- GATE 2019 CS Q48 – 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…
- GATE 2026 CS (CS2) Q37 – 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…
- GATE 2026 CS (CS1) Q41 – 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…
- GATE 2026 CS (CS1) Q49 – 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…
- GATE 2026 CS (CS1) Q50 – 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…
- GATE 2025 CS (CS2) Q29 – Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?
- GATE 2025 CS (CS2) Q37 – 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…
- GATE 2025 CS (CS2) Q59 – 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…
- GATE 2025 CS (CS1) Q18 – 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…
- GATE 2025 CS (CS1) Q43 – 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…
- GATE 2025 CS (CS1) Q64 – 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…
- GATE 2024 CS (CS2) Q59 – 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…
- GATE 2024 CS (CS1) Q45 – 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)…
- GATE 2024 CS (CS1) Q60 – 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…
- GATE 2023 CS Q56 – 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…
- GATE 2022 CS Q49 – Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning…
- GATE 2021 CS (CS1) Q27 – 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…
- GATE 2021 CS (CS1) Q46 – 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…
- GATE 2021 CS (CS1) Q51 – 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…
- GATE 2020 CS Q41 – 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…
- GATE 2020 CS Q50 – 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…
- GATE 2020 CS Q59 – 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…