Graph Traversals, Topological Sort and Connectivity: GATE CS previous year questions (Algorithms)

GATE CS 2026 Set 1MSQ2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.50
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G (V, E)$ as input, where $d [v]$ and $f [v]$ are the discovery time and fini...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2026 Set 1MSQ2 marksEasy (estimate)
GATE CS 2026 Set 1, Q.55
An undirected, unweighted, simple graph $G (V, E)$ is said to be 2-colorable if there exists a function $c : V \to {0, 1}$ such that for every $(u, v) \in E$ …
Graph Traversals, Topological Sort and Connectivity
GATE CS 2025 Set 1MCQ2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.43
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$ in $V$ . Let the m...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2025 Set 2MSQ1 markMedium (estimate)
GATE CS 2025 Set 2, Q.29
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?
Graph Traversals, Topological Sort and Connectivity
GATE CS 2025 Set 2NAT2 marksMedium (estimate)
GATE CS 2025 Set 2, Q.59
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 v. Let u be a vertex i...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2024 Set 1MSQ2 marksMedium (estimate)
GATE CS 2024 Set 1, Q.45
Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ ,...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2024 Set 1NAT2 marksEasy (estimate)
GATE CS 2024 Set 1, Q.60
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 components in $G$ is _________
Graph Traversals, Topological Sort and Connectivity
GATE CS 2023NAT2 marksMedium (estimate)
GATE CS 2023, Q.56
Let $U = {1, 2, 3}$ . Let $2^{U}$ denote the powerset of $U$ . Consider an undirected graph $G$ whose vertex set is $2^{U}$ . For any $A, B \in 2^{U}$ , $(A, B)$ is an edge in $G$ if an...
Graph Theory · Graph Traversals, Topological Sort and Connectivity
GATE CS 2021 Set 1MSQ2 marksMedium (estimate)
GATE CS 2021 Set 1, Q.51 (CS Q.41)
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 connected components. Let $T$ ...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2021 Set 2MSQ2 marksMedium (estimate)
GATE CS 2021 Set 2, Q.56 (CS Q.46)
Consider the following directed graph: A 4 by 4 directed grid graph with 16 solid black vertices and directed edges between adjacent vertices. The bottom-left vertex is labeled...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2020MCQ2 marksMedium (estimate)
GATE CS 2020, Q.41 (CS Q.31)
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 edge…
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
GATE CS 2020MCQ2 marksMedium (estimate)
GATE CS 2020, Q.50 (CS Q.40)
Let $G = (V, E)$ be a directed, weighted graph with weight function $w : E \to R$ . For some function $f : V \to R$ , for each edge $(u, v) \in E$ , define…
Graph Traversals, Topological Sort and Connectivity
GATE CS 2020NAT2 marksEasy (estimate)
GATE CS 2020, Q.59 (CS Q.49)
Consider a graph $G = (V, E)$ , where $V = {v_{1}, v_{2}, \dots, v_{100}}$ , $E = {(v_{i}, v_{j}) ∣ 1 \leq i < j \leq 100}$ , and weight of the edge $(v_{i}, v_{j})$ is $∣ i - j ∣$ . The wei...
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
GATE CS 2018MCQ2 marksMedium (estimate)
GATE CS 2018, Q.40 (CS Q.30)
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 statements. (I) No e...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2017 Set 2MCQ1 markMedium (estimate)
GATE CS 2017 Set 2, Q.15 (CS Q.15)
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph b...
Graph Traversals, Topological Sort and Connectivity · Graph Representations and Disjoint Sets
GATE CS 2016 Set 1NAT1 markMedium (estimate)
GATE CS 2016 Set 1, Q.21 (CS Q.11)
Consider the following directed graph: Directed acyclic graph with six vertices labeled a, b, c, d, e, and f. Directed edges are from a to b, a to d, b to c, d to e, c to f, and...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2016 Set 2NAT1 markMedium (estimate)
GATE CS 2016 Set 2, Q.21 (CS Q.11)
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n$ -th vertex in thi...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2015 Set 1MCQ2 marksMedium (estimate)
GATE CS 2015 Set 1, Q.55 (CS Q.45)
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$ , let $d (x)$ denote the shortest distance in $G$ from $s$ to...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2014 Set 1MCQ1 markEasy (estimate)
GATE CS 2014 Set 1, Q.13 (CS Q.3)
Let $G = (V, E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2014 Set 1MCQ1 markEasy (estimate)
GATE CS 2014 Set 1, Q.21 (CS Q.11)
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$ , when $G$ is represented as an adjacency ma...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2014 Set 1MCQ1 markEasy (estimate)
GATE CS 2014 Set 1, Q.23 (CS Q.13)
Consider the directed graph given below. Directed graph on four vertices P, Q, R, and S Which one of the following is TRUE?
Graph Traversals, Topological Sort and Connectivity
GATE CS 2014 Set 2MCQ1 markEasy (estimate)
GATE CS 2014 Set 2, Q.24 (CS Q.14)
Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for comp...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2014 Set 3NAT1 markHard (estimate)
GATE CS 2014 Set 3, Q.23 (CS Q.13)
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that...
Graph Traversals, Topological Sort and Connectivity
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.29 (CS Q.29)
Let $G$ be a weighted graph with edge weights greater than one and $G^{'}$ be the graph constructed by squaring the weights of edges in $G$ . Let $T$ and $T^{'}$ be the minimum spannin...
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity

Questions

Other topics of Algorithms