Graph Traversal, Connectivity and Directed Graphs PYQs for GATE CS

Solve 10+ Graph Traversal, Connectivity and Directed Graphs previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Graph Traversal and Connectivity

Chapter Roadmap

Graph Traversal, Connectivity and Directed Graphs

1. Breadth-First Search Trees and Applications Shortest paths, level-by-level exploration, and tree diameter. Current

2. Depth-First Search Edges and Timestamps Discovery and finish times, edge classification, and topological sorting.

3. Connected Components and Articulation Points Graph connectivity, bridges, and critical nodes.

4. Directed Graphs, Cycles and Strong Connectivity Directed acyclic graphs, strongly connected components, and Kosaraju algorithm.

5. Greedy Graph Coloring Chromatic number, Welch-Powell algorithm, and upper bounds.

By the end of this chapter, you will master the traversal techniques that form the backbone of graph problems in competitive exams.

Breadth-First Search Trees and Applications

The definitive structure for finding shortest paths in unweighted graphs and solving distance-based puzzles.

What you will learn here:

How BFS constructs a tree of shortest paths from a source
Edge classification rules specific to BFS traversal
The elegant two-BFS method for finding tree diameter
Solving complex subset-graph traversal problems

Chapter: Graph Traversal, Connectivity and Directed Graphs → Topic 1 of 5

Graph Traversal, Connectivity and Directed Graphs: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Algorithms · 2026_Set1 MSQ

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 finishing time, respectively, of the vertex

v \in V

D F S (G) :

unmark all

v \in V

t \leftarrow 0

for each

v \in V

v

is unmarked

t \leftarrow E x pl or e (G, v, t)

end if
end for

E x pl or e (G, v, t) :

mark

v

t \leftarrow t + 1

d [v] \leftarrow t

for each

(v, w) \in E

w

is unmarked

t \leftarrow E x pl or e (G, w, t)

    end if
  end for

t \leftarrow t + 1

f [v] \leftarrow t

return

t

Suppose that the input directed graph

G (V, E)

is a directed acyclic graph (DAG).

For an edge

(u, v) \in E

, which of the following options will NEVER be correct?

A.
$d [u] < d [v] < f [v] < f [u]$
B.
$d [v] < d [u] < f [u] < f [v]$
C.
$d [v] < f [v] < d [u] < f [u]$
D.
$d [u] < d [v] < f [u] < f [v]$

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is a "DFS timestamp and DAG properties" question, recognisable because it asks which timestamp relationships are impossible for an edge in a Directed Acyclic Graph.

Step 1: Understand the Parenthesis Theorem.

For any two vertices $u$ and $v$ in a DFS traversal, their discovery/finish intervals $[d [u], f [u]]$ and $[d [v], f [v]]$ must be either completely disjoint or perfectly nested. They can never partially overlap.

Step 2: Evaluate Option D.

$d [u] < d [v] < f [u] < f [v]$ represents partially overlapping intervals. This violates the Parenthesis Theorem and is impossible in ANY DFS traversal, regardless of whether the graph is a DAG. Thus, Option D will NEVER be correct.

Step 3: Evaluate Option B.

$d [v] < d [u] < f [u] < f [v]$ represents perfectly nested intervals where $v$ is an ancestor of $u$ . This means the edge $(u, v)$ goes from a descendant to an ancestor, which is the definition of a back edge. A back edge implies the existence of a cycle. Since the input graph is a DAG (Directed Acyclic Graph), it cannot contain any cycles, and therefore cannot contain any back edges. Thus, Option B will NEVER be correct.

Step 4: Evaluate Options A and C.

Option A ( $d [u] < d [v] < f [v] < f [u]$ ) represents nested intervals where $u$ is an ancestor of $v$ . This corresponds to a tree edge or forward edge, which are perfectly valid in a DAG.

Option C ( $d [v] < f [v] < d [u] < f [u]$ ) represents disjoint intervals where $v$ is completely finished before $u$ is discovered. This corresponds to a cross edge, which is also valid in a DAG.

Answer: B, D

Question 2 · Algorithms · 2025_Set2 MSQ

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?

A.
A DFS tree of $G$ is a Shortest Path tree of $G$ .
B.
Every non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.
C.
If $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source vertex $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.
D.
Both BFS and DFS can be used to find the connected components of $G$ .

Correct Answer:

["C","D"]

Step-by-Step Solution

Key idea: This is a "BFS vs DFS properties" question, recognisable because it asks to identify universally true statements about tree and non-tree edges in undirected graphs.

Step 1: Evaluate Option A.

"A DFS tree of G is a Shortest Path tree of G."

This is FALSE. A Breadth-First Search (BFS) tree guarantees shortest paths from the source in an unweighted graph. A DFS tree does not; it prioritizes depth over distance.

Step 2: Evaluate Option B.

"Every non-tree edge of G with respect to a DFS tree is a forward/back edge."

This is FALSE. In an undirected graph, a DFS classifies every edge as either a tree edge or a back edge. Forward edges and cross edges do not exist in undirected DFS. Stating it is a "forward/back edge" is incorrect because it can never be a forward edge.

Step 3: Evaluate Option C.

"If (u,v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within $\pm 1$ of each other."

This is TRUE. In a BFS tree, vertices are explored level by level. An edge in the original graph can only connect vertices in the same level or in adjacent levels. Therefore, their distances from the source differ by at most 1.

Step 4: Evaluate Option D.

"Both BFS and DFS can be used to find the connected components of G."

This is TRUE. Both traversal algorithms will visit all vertices reachable from a starting vertex. By repeatedly starting a new traversal from an unvisited vertex, both BFS and DFS can correctly identify all connected components.

Answer: C, D

Question 3 · Algorithms · 2025_Set2 NAT

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 in G at maximum distance from
       v as given by the BFS.
    2. Run BFS on G again with u as the starting vertex.
       Let z be the vertex at maximum distance from u as
       given by the BFS.
    3. Output the distance between u and z in G.

The output of someAlgo(

T

) for the tree shown in the given figure is ___________. (Answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a "tree diameter via two-BFS" question, recognisable because the algorithm runs BFS twice, each time picking the vertex at maximum distance, and outputs the final distance.

Step 1: Understand the algorithm.

The given algorithm is the standard linear-time method to find the diameter of a tree. The first BFS finds one endpoint of a longest path (a diameter), and the second BFS finds the other endpoint and the length of this path.

Step 2: Trace the tree structure from the given figure.

The vertices and edges form a tree. Let's trace the longest path.

Starting from the rightmost leaf (v14 at 650, 172), the path to the leftmost leaf (v4 at 65, 245) is:

v14 → v13 → v11 → v8 → v2 → v3 → v4.

Step 3: Count the edges in this path.

v14 to v13
v13 to v11
v11 to v8
v8 to v2
v2 to v3
v3 to v4

This path has exactly 6 edges. Checking other leaf-to-leaf paths (e.g., v14 to v6 or v14 to v7) also yields a maximum length of 6.

Step 4: Conclude the output.

Since the algorithm computes the tree diameter, and the diameter of this tree is 6, the output is 6.

Answer: 6

Question 4 · Algorithms · 2025_Set1 MCQ

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 maximum value of $d (u, v)$ , $u, v \in V$ such that $u \neq = v$ , be 30. Let $T$ be any breadth-first-search tree of $G$ . Which ONE of the given options is CORRECT for every such graph $G$ ?

A.
The height of $T$ is exactly 15.
B.
The height of $T$ is exactly 30.
C.
The height of $T$ is at least 15.
D.
The height of $T$ is at least 30.

Correct Answer:

Step-by-Step Solution

Key idea: This is a "BFS tree height vs graph diameter" question, recognisable because it relates the maximum distance in the graph (diameter) to the height of an arbitrary BFS tree.

Step 1: Define the given parameters.

The graph $G$ has a maximum distance (diameter) of 30. Let $u$ and $v$ be the vertices such that $d (u, v) = 30$ .

Let $T$ be a BFS tree rooted at some arbitrary vertex $r$ .

Step 2: Apply the triangle inequality.

In any graph, the shortest path distance satisfies the triangle inequality:

$d (u, v) \leq d (u, r) + d (r, v)$

Substituting the known diameter:

$30 \leq d (u, r) + d (r, v)$

Step 3: Bound the maximum distance from $r$ .

For the sum of two non-negative integers to be at least 30, at least one of them must be at least 15. Therefore:

$max (d (u, r), d (r, v)) \geq 15$

Step 4: Relate to BFS tree height.

In a BFS tree rooted at $r$ , the distance from $r$ to any vertex $x$ in the tree is exactly the shortest path distance $d (r, x)$ in $G$ .

The height of $T$ is the maximum distance from $r$ to any vertex in $T$ . Thus:

$Height (T) = x \in V max d (r, x) \geq max (d (u, r), d (r, v)) \geq 15$

Step 5: Evaluate the options.

The height can be exactly 15 (e.g., if $G$ is a path of 31 vertices and $r$ is the middle vertex). It is not necessarily 30 or greater than 30. Thus, "at least 15" is the only statement guaranteed to be true for every such graph and every BFS tree.

Answer: C

Question 5 · Algorithms · 2024_Set1 MSQ

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$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

A.
There are no back-edges in $G$ with respect to the tree $T$
B.
There are no cross-edges in $G$ with respect to the tree $T$
C.
There are no forward-edges in $G$ with respect to the tree $T$
D.
The only edges in $G$ are the edges in $T$

Correct Answer:

["C"]

Step-by-Step Solution

Key idea: This is a "DFS and BFS tree equivalence" question, recognisable because it states that a single tree $T$ serves as both the DFS and BFS spanning tree for a directed graph $G$ , and asks what this implies about non-tree edges.

Step 1: Analyze the implications of $T$ being a BFS tree.

In a BFS tree rooted at $v$ , the depth of any vertex $y$ is the length of the shortest path from $v$ to $y$ . For any edge $(x, y)$ in $G$ , BFS guarantees that $depth (y) \leq depth (x) + 1$ .

Step 2: Analyze the implications of $T$ being a DFS tree.

In a DFS tree, non-tree edges can be back edges, forward edges, or cross edges.

Step 3: Evaluate Option C (Forward edges).

Suppose there is a forward edge $(x, y)$ in $G$ . By definition of a DFS forward edge, $y$ is a proper descendant of $x$ in $T$ . This means the path in $T$ from $x$ to $y$ has length $k \geq 2$ .

Therefore, $depth (y) = depth (x) + k \geq depth (x) + 2$ .

However, since $(x, y)$ is an edge in $G$ , the BFS property requires $depth (y) \leq depth (x) + 1$ .

This is a contradiction ( $depth (x) + 2 \leq depth (x) + 1$ is false). Thus, there can be NO forward edges. Option C is TRUE.

Step 4: Evaluate Options A, B, and D with counterexamples.

Back edges (Option A): Consider $G$ with edges $v \to a$ , $a \to b$ , $b \to a$ . DFS tree from $v$ is $(v, a), (a, b)$ . BFS tree from $v$ is also $(v, a), (a, b)$ . The edge $(b, a)$ is a back edge. So A is FALSE.
Cross edges (Option B): Consider $G$ with edges $v \to a$ , $v \to b$ , $b \to a$ . DFS tree from $v$ (visiting $a$ then $b$ ) is $(v, a), (v, b)$ . BFS tree is also $(v, a), (v, b)$ . The edge $(b, a)$ is a cross edge. So B is FALSE.
Only tree edges (Option D): The counterexamples above show non-tree edges can exist. So D is FALSE.

Answer: C

Question 6 · Algorithms · 2024_Set1 NAT

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 _________

Correct Answer:

Step-by-Step Solution

Key idea: This is a "counting connected components via DFS forest" question, recognisable because it provides the total number of vertices and the number of tree edges in a DFS forest.

Step 1: Recall the relationship between vertices, tree edges, and components.

When DFS is run on an undirected graph $G = (V, E)$ , it produces a DFS forest. Each tree in this forest corresponds to exactly one connected component.

Step 2: Apply the tree edge formula.

For any tree with $k$ vertices, there are exactly $k - 1$ tree edges.

If the graph has $C$ connected components, and the $i$ -th component has $k_{i}$ vertices, the total number of vertices is $∣ V ∣ = \sum k_{i}$ .

The total number of tree edges is $E_{tree} = \sum (k_{i} - 1) = \sum k_{i} - \sum 1 = ∣ V ∣ - C$ .

Step 3: Rearrange to solve for $C$ .

$C = ∣ V ∣ - E_{tree}$

Step 4: Substitute the given values.

We are given $∣ V ∣ = 100$ and $E_{tree} = 40$ .

$C = 100 - 40 = 60$

Answer: 60

Question 7 · Algorithms · 2023 NAT

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 and only if (i)

A \neq = B

, and (ii) either

A \subseteq B

B \subseteq A

. For any vertex

A

G

, the set of all possible orderings in which the vertices of

G

can be visited in a Breadth First Search (BFS) starting from

A

is denoted by

B (A)

.

If

\emptyset

denotes the empty set, then the cardinality of

B (\emptyset)

is __________.

Question 8 · Algorithms · 2023 MSQ

Let

G

be a simple, finite, undirected graph with vertex set

{v_{1}, \dots, v_{n}}

. Let

Δ (G)

denote the maximum degree of

G

and let

N = {1, 2, \dots}

denote the set of all possible colors. Color the vertices of

G

using the following greedy strategy:

for i = 1, \dots, n

color (v_{i}) \leftarrow min {j \in N : no neighbour of v_{i} is colored j}

Which of the following statements is/are TRUE?

A.
This procedure results in a proper vertex coloring of $G$ .
B.
The number of colors used is at most $Δ (G) + 1$ .
C.
The number of colors used is at most $Δ (G)$ .
D.
The number of colors used is equal to the chromatic number of $G$ .

Correct Answer:

["A","B"]

Step-by-Step Solution

Key idea: This is a "greedy graph coloring properties" question, recognisable because it describes the standard sequential greedy coloring algorithm and asks for its theoretical guarantees.

Step 1: Evaluate Option A.

"This procedure results in a proper vertex coloring of G."

By definition, the algorithm assigns to each vertex $v_{i}$ the smallest positive integer $j$ that is not used by any of its already-colored neighbors. This ensures no two adjacent vertices share the same color. Thus, it always produces a proper vertex coloring. Option A is TRUE.

Step 2: Evaluate Option B.

"The number of colors used is at most $Δ (G) + 1$ ."

When coloring vertex $v_{i}$ , it has at most $Δ (G)$ neighbors. Therefore, at most $Δ (G)$ colors are forbidden for $v_{i}$ . Since we choose from the infinite set $N$ , there is always at least one available color in the set ${1, 2, \dots, Δ (G) + 1}$ . Thus, the algorithm never needs more than $Δ (G) + 1$ colors. Option B is TRUE.

Step 3: Evaluate Option C.

"The number of colors used is at most $Δ (G)$ ."

This is FALSE. Consider a complete graph $K_{n}$ . Here, $Δ (G) = n - 1$ . However, every vertex is connected to every other vertex, so the greedy algorithm (regardless of ordering) will use exactly $n$ colors. Since $n = Δ (G) + 1$ , it exceeds $Δ (G)$ .

Step 4: Evaluate Option D.

"The number of colors used is equal to the chromatic number of G."

This is FALSE. The greedy algorithm's performance heavily depends on the vertex ordering. For example, a bipartite graph (chromatic number 2) can be forced to use $n /2$ colors if the vertices are ordered such that each new vertex is connected to all previously colored vertices in the opposite partition.

Answer: A, B

Question 9 · Algorithms · 2021_Set2 MSQ

Consider the following directed graph:

Which of the following is/are correct about the graph?

A.
The graph does not have a topological order.
B.
A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges.
C.
The graph does not have a strongly connected component.
D.
For each pair of vertices $u$ and $v$ , there is a directed path from $u$ to $v$ .

Correct Answer:

["A","B"]

Step-by-Step Solution

Key idea: This is a "directed graph properties and DFS classification" question, recognisable because it asks to evaluate structural properties (topological order, SCCs) and DFS edge classifications on a specific grid-like directed graph.

Step 1: Analyze Option A (Topological Order).

A directed graph has a topological order if and only if it is a Directed Acyclic Graph (DAG).

Let's check for cycles. Consider the vertices in the top two rows, columns 2 and 3:

R1C2 → R2C2 → R2C3 → R1C3 → R1C2.

This forms a directed cycle of length 4. Since the graph contains a cycle, it is not a DAG and does not have a topological order. Option A is TRUE.

Step 2: Analyze Option C (Strongly Connected Components).

Every directed graph has at least one Strongly Connected Component (SCC). Even a single vertex with no cycles forms an SCC of size 1. Therefore, the statement "does not have an SCC" is fundamentally false. Option C is FALSE.

Step 3: Analyze Option D (Universal Reachability).

This option claims the graph is strongly connected (a path exists between every pair of vertices). However, vertex R1C4 is a sink (it has incoming edges but no outgoing edges). No path can start from R1C4 to reach any other vertex. Thus, the graph is not strongly connected. Option D is FALSE.

Step 4: Analyze Option B (DFS Back Edges).

A standard DFS starting from S (which is R4C1, the bottom-left vertex) explores the graph.

The graph contains three disjoint fundamental cycles that will each yield exactly one back edge in a standard left-to-right, top-to-bottom DFS traversal:

R4C1 → R4C2 → R3C2 → R3C1 → R4C1 (yields back edge R3C1 → R4C1)
R4C3 → R4C4 → R3C4 → R3C3 → R4C3 (yields back edge R3C3 → R4C3)
R1C2 → R2C2 → R2C3 → R1C3 → R1C2 (yields back edge R2C2 → R2C3)

A careful trace of DFS confirms exactly three back edges are classified. Option B is TRUE.

Answer: A, B

Question 10 · Algorithms · 2021_Set1 MSQ

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

be a DFS tree obtained by doing DFS in a connected undirected graph

G

.
Which of the following options is/are correct?

A.
Root of $T$ can never be an articulation point in $G$ .
B.
Root of $T$ is an articulation point in $G$ if and only if it has 2 or more children.
C.
A leaf of $T$ can be an articulation point in $G$ .
D.
If $u$ is an articulation point in $G$ such that $x$ is an ancestor of $u$ in $T$ and $y$ is a descendent of $u$ in $T$ , then all paths from $x$ to $y$ in $G$ must pass through $u$ .

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is an "articulation point properties" question, recognisable because it asks to evaluate structural conditions for articulation points within a DFS tree of an undirected graph.

Step 1: Evaluate Option A and B (Root conditions).

The root of a DFS tree is an articulation point if and only if it has two or more children. If it has only one child, removing the root leaves the rest of the tree connected. If it has $\geq 2$ children, those subtrees have no cross edges between them (otherwise they would have been discovered in a single subtree), so removing the root disconnects them.

Thus, Option A is FALSE, and Option B is TRUE.

Step 2: Evaluate Option C (Leaf conditions).

A leaf in a DFS tree has no descendants. Removing a leaf only removes that single vertex; it cannot disconnect any other pair of vertices in the graph. Therefore, a leaf can never be an articulation point. Option C is FALSE.

Step 3: Evaluate Option D (Path conditions).

If $u$ is an articulation point, its removal disconnects the graph. In a DFS tree, if $x$ is an ancestor of $u$ and $y$ is a descendant of $u$ , any path between $x$ and $y$ in the original graph $G$ must pass through $u$ . If there were a path bypassing $u$ , it would imply a back edge or cross edge connecting a descendant of $u$ to an ancestor of $u$ (or another branch), which would have been traversed during DFS, making $u$ not an articulation point. Option D is TRUE.

Answer: B, D

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Graph Traversal, Connectivity and Directed Graphs PYQs for GATE CS

Chapter Roadmap: Graph Traversal and Connectivity

Chapter Roadmap

Breadth-First Search Trees and Applications

Breadth-First Search Trees and Applications

What you will learn here:

Graph Traversal, Connectivity and Directed Graphs: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit