GATE DA Graph Algorithms Previous Year Questions

GATE DA 2025 | Question 58

MSQ · 2 marks

Let \(G\) be a simple, unweighted, and undirected graph. A subset of the vertices and edges of \(G\) are shown below.

Eight vertices in two rows, a, b, c, d on top and e, f, g, h below. Edges join a and b, b and c, c and d, e and f, f and g, g and h, and also a and f, f and c, and c and h.

It is given that \(a - b - c - d\) is a shortest path between \(a\) and \(d\); \(e - f - g - h\) is a shortest path between \(e\) and \(h\); \(a - f - c - h\) is a shortest path between \(a\) and \(h\). Which of the following is/are NOT the edges of \(G\)?

\((b, d)\) \((b, g)\) \((b, h)\) \((e, g)\)

Explanation

Answer: (A), (C), (D)

Each given shortest path has 3 edges, so in \(G\) the distances between \(a\) and \(d\), \(e\) and \(h\), and \(a\) and \(h\) are all exactly 3. An edge that would create a path of length 2 between one of these pairs cannot be in \(G\).

\((b, d)\) would give \(a - b - d\), of length 2 between \(a\) and \(d\). Not an edge.
\((b, h)\) would give \(a - b - h\), of length 2 between \(a\) and \(h\). Not an edge.
\((e, g)\) would give \(e - g - h\), of length 2 between \(e\) and \(h\). Not an edge.
\((b, g)\) shortens none of the three distances (for example, \(a - b - g - h\) still has length 3), so it may be an edge of \(G\).

Answer: A, C, D

GATE DA 2025 | Question 65

NAT · 2 marks

Consider a directed graph \(G = (V, E)\), where \(V = \{0, 1, 2, \ldots, 100\}\) and \(E = \{(i, j) : 0 < j - i \le 2, \text{ for all } i, j \in V\}\). Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is ________ (Answer in integer)

Your answer

Explanation

Answer: 75

Each vertex \(i\) has edges only to \(i + 2\) and \(i + 1\), listed in that order. So DFS from 0 always follows the \(+2\) edge first: 0, 2, 4, …, 100. Vertex 100 has no outgoing edges, so DFS backtracks to 98, whose second neighbour 99 is new; back at 96 it finds 97, and so on down to 1.

The discovery order is 0, 2, 4, …, 100, then 99, 97, …, 1. Vertex 50 is the 26th vertex discovered, so the other \(101 - 26 = 75\) vertices come after it: the 25 even vertices 52 to 100 and all 50 odd vertices.

Answer: 75

GATE DA 2024 | Question 14

MCQ · 1 mark · −0.33

Consider performing depth-first search (DFS) on an undirected and unweighted graph \(G\) starting at vertex \(s\). For any vertex \(u\) in \(G\), \(d[u]\) is the length of the shortest path from \(s\) to \(u\). Let \((u, v)\) be an edge in \(G\) such that \(d[u] < d[v]\). If the edge \((u, v)\) is explored first in the direction from \(u\) to \(v\) during the above DFS, then \((u, v)\) becomes a ______ edge.

tree cross back gray

Explanation

Answer: (A)

In a DFS of an undirected graph, every edge ends up as either a tree edge or a back edge. Cross (and forward) edges cannot occur: a vertex finishes only after all of its edges have been explored, so the far end of a newly explored edge is never already finished. Gray is the colour of a vertex that is discovered but not finished, not a kind of edge. So (B) and (D) are out.

The key reads "explored first in the direction from \(u\) to \(v\)" as the search moving from \(u\), the end nearer to \(s\), along this edge out to \(v\). DFS moves along an edge only to a vertex it has not discovered yet, so \(v\) is discovered through \((u, v)\) and the edge becomes a tree edge. A back edge, (C), would need \(v\) to be discovered already, and then the search does not move to \(v\) at all.

Answer: A

GATE DA 2024 | Question 51

MSQ · 2 marks

Consider the directed acyclic graph (DAG) below:

Directed graph with seven vertices: P and R each have an edge into Q, Q has edges to S and V, S has an edge to U, and V has an edge to T.

Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

P Q R S T U V P R Q V S U T P Q R S V U T P R Q S V T U

Explanation

Answer: (B), (D)

In a topological order every edge points forward, so each vertex comes after all of its predecessors. The edges are \(P \to Q\), \(R \to Q\), \(Q \to S\), \(Q \to V\), \(S \to U\) and \(V \to T\): P and R must precede Q, Q must precede S and V, S must precede U, and V must precede T.

A and C fail: both place Q before R, which breaks the edge \(R \to Q\).
B holds: after P, R, Q come V, S, U, T, so U follows S and T follows V.
D holds: P, R, Q, S, V, T, U also respects every edge.

More than one order is valid because the chains \(S \to U\) and \(V \to T\) do not depend on each other.

Answer: B, D