Crack
GATE
C
G
Topic
Graph Algorithms
Algorithms
0
/ 23 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2
3
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
1
0.3
0
0.7
2018
0
0
0
0
2019
0
0
0
0
2020
2
1
0
1
2021
2.5
0.5
1
1
2022
1
0
1
0
2023
0
0
0
0
2024
1.5
0
0.5
1
2025
3
1.5
0.5
1
2026
1.5
0.5
1
0
1
CS 2026 Set 1 · 2 marks · MSQ · Hard
Let
G
(
V
,
E
)
G(V, E)
G
(
V
,
E
)
be a simple, undirected, edge-weighted graph with unique edge weights.
2
CS 2026 Set 1 · 2 marks · MSQ · Hard
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph
G
(
V
,
E
)
G(V, E)
G
(
V
,
E
)
as input, where
d
[
v
]
d[v]
d
[
v
]
and
f
[
v
]
f[v]
f
[
v
]
are the discovery time and finishing time, respectively, of the vertex
v
∈
V
v \in V
v
∈
V
.
3
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Consider a complete graph
K
n
K_n
K
n
with
n
n
n
vertices (
n
>
4
n > 4
n
>
4
). Note that multiple spanning trees can be constructed over
K
n
K_n
K
n
. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.
4
CS 2025 Set 1 · 1 mark · MCQ · Easy
Let
G
G
G
be any undirected graph with positive edge weights, and
T
T
T
be a minimum spanning tree of
G
G
G
. For any two vertices,
u
u
u
and
v
v
v
, let
d
1
(
u
,
v
)
d_1(u, v)
d
1
(
u
,
v
)
and
d
2
(
u
,
v
)
d_2(u, v)
d
2
(
u
,
v
)
be the shortest distances between
u
u
u
and
v
v
v
in
G
G
G
and
T
T
T
, respectively. Which ONE of the options is CORRECT for all possible
G
,
T
,
u
G, T, u
G
,
T
,
u
and
v
v
v
?
5
CS 2025 Set 1 · 2 marks · MCQ · Hard
Let
G
(
V
,
E
)
G(V,E)
G
(
V
,
E
)
be an undirected and unweighted graph with
100
100
100
vertices. Let
d
(
u
,
v
)
d(u,v)
d
(
u
,
v
)
denote the number of edges in a shortest path between vertices
u
u
u
and
v
v
v
in
V
V
V
. Let the maximum value of
d
(
u
,
v
)
d(u,v)
d
(
u
,
v
)
,
u
,
v
∈
V
u,v \in V
u
,
v
∈
V
such that
u
≠
v
u \neq v
u
=
v
, be
30
30
30
. Let
T
T
T
be any breadth-first-search tree of
G
G
G
. Which ONE of the given options is CORRECT for every such graph
G
G
G
?
6
CS 2025 Set 1 · 2 marks · NAT · Moderate
The maximum value of
x
x
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 integer)
7
CS 2025 Set 2 · 1 mark · MSQ · Moderate
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph
G
G
G
is/are TRUE?
8
CS 2025 Set 2 · 2 marks · MCQ · Moderate
Let
G
G
G
be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant
α
\alpha
α
is added to the weight of every edge.
9
CS 2025 Set 2 · 2 marks · NAT · Moderate
Consider the following algorithm
s
o
m
e
A
l
g
o
\mathtt{someAlgo}
someAlgo
that takes an undirected graph
G
G
G
as input.
10
CS 2024 Set 1 · 2 marks · MSQ · Moderate
Let
G
G
G
be a directed graph and
T
T
T
a depth first search (DFS) spanning tree in
G
G
G
that is rooted at a vertex
v
v
v
. Suppose
T
T
T
is also a breadth first search (BFS) tree in
G
G
G
, rooted at
v
v
v
. Which of the following statements is/are TRUE for every such graph
G
G
G
and tree
T
T
T
?
11
CS 2024 Set 1 · 2 marks · NAT · Easy
The number of edges present in the forest generated by the DFS traversal of an undirected graph
G
G
G
with 100 vertices is 40. The number of connected components in
G
G
G
is ____
12
CS 2024 Set 2 · 2 marks · NAT · Moderate
The number of distinct minimum-weight spanning trees of the following graph is ____\n
13
CS 2022 · 2 marks · MSQ · Moderate
Consider a simple undirected weighted graph
G
G
G
, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of
G
G
G
is/are TRUE?
14
CS 2021 Set 1 · 1 mark · NAT · Moderate
Consider the following undirected graph with edge weights as shown:
15
CS 2021 Set 1 · 2 marks · MSQ · Moderate
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.
16
CS 2021 Set 2 · 1 mark · MCQ · Moderate
Let
G
G
G
be a connected undirected weighted graph. Consider the following two statements.
17
CS 2021 Set 2 · 1 mark · NAT · Moderate
Consider a complete binary tree with 7 nodes. Let
A
A
A
denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let
B
B
B
denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
18
CS 2021 Set 2 · 2 marks · MSQ · Hard
Consider the following directed graph:
19
CS 2020 · 2 marks · MCQ · Moderate
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be a weighted undirected graph and let
T
T
T
be a Minimum Spanning Tree (MST) of
G
G
G
maintained using adjacency lists. Suppose a new weighted edge
(
u
,
v
)
∈
V
×
V
(u, v) \in V \times V
(
u
,
v
)
∈
V
×
V
is added to
G
G
G
. The worst case time complexity of determining if
T
T
T
is still an MST of the resultant graph is
20
CS 2020 · 2 marks · NAT · Moderate
Consider a graph
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
, where
V
=
{
v
1
,
v
2
,
…
,
v
100
}
V = \{v_1, v_2, \dots, v_{100}\}
V
=
{
v
1
,
v
2
,
…
,
v
100
}
,
E
=
{
(
v
i
,
v
j
)
∣
1
≤
i
<
j
≤
100
}
E = \{(v_i, v_j) \mid 1 \le i < j \le 100\}
E
=
{(
v
i
,
v
j
)
∣
1
≤
i
<
j
≤
100
}
, and weight of the edge
(
v
i
,
v
j
)
(v_i, v_j)
(
v
i
,
v
j
)
is
∣
i
−
j
∣
|i - j|
∣
i
−
j
∣
. The weight of minimum spanning tree of
G
G
G
is ____.
21
CS 2015 Set 1 · 2 marks · MCQ · Moderate
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be a simple undirected graph, and
s
s
s
be a particular vertex in it called the source. For
x
∈
V
x \in V
x
∈
V
, let
d
(
x
)
d(x)
d
(
x
)
denote the shortest distance in
G
G
G
from
s
s
s
to
x
x
x
. A breadth first search (BFS) is performed starting at
s
s
s
. Let
T
T
T
be the resultant BFS tree. If
(
u
,
v
)
(u,v)
(
u
,
v
)
is an edge of
G
G
G
that is not in
T
T
T
, then which one of the following CANNOT be the value of
d
(
u
)
−
d
(
v
)
d(u) - d(v)
d
(
u
)
−
d
(
v
)
?
22
CS 2015 Set 1 · 2 marks · NAT · Hard
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
)
,
(
B
,
C
)
,
(
B
,
E
)
,
(
E
,
F
)
,
(
D
,
F
)
}
\{(A, C), (B, C), (B, E), (E, F), (D, F)\}
{(
A
,
C
)
,
(
B
,
C
)
,
(
B
,
E
)
,
(
E
,
F
)
,
(
D
,
F
)}
. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ________.
23
CS 2015 Set 3 · 2 marks · NAT · Easy
Let
G
G
G
be a connected undirected graph of
100
100
100
vertices and
300
300
300
edges. The weight of a minimum spanning tree of
G
G
G
is
500
500
500
. When the weight of each edge of
G
G
G
is increased by five, the weight of a minimum spanning tree becomes ____.