GATE Algorithms: Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths – Previous Year Questions
32 GATE previous year questions on Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths (Algorithms, Computer Science) with answers and explanations, from every paper.
- GATE 2017 CS 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 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 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 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 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 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 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 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 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 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 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…