chapter

Graph Traversal: BFS and DFS Notes for GATE DA

Graph Traversal: BFS and DFS notes for GATE DA: 25 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

graph traversal bfs and dfs notes

Chapter Roadmap: Graph Traversal

.smart-card { font-family: system-ui, -apple-system, sans-serif; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); border-radius: 12px; padding: 1.5rem; line-height: 1.6; } .smart-card h3 { color: var(--color-primary); margin-top: 0; font-size: 1.1rem; } .smart-card ul { padding-left: 1.2rem; } .smart-card li { margin-bottom: 0.5rem; } Chapter Roadmap: Graph Traversal 1. Reachability in Directed Graphs Forward and reverse reachability, SCCs 2. DFS Discovery and Edge Classification Tree edges, back edges, cross edges 3. Graph Traversal on Given Diagrams Visual tracing and structural properties What you will master How directed edges break the symmetry of connectivity. Using reverse graphs to find strongly connected components. Classifying edges discovered during Depth First Search. Accurately tracing traversals on complex visual diagrams.

Reachability in Directed Graph Traversals

.smart-card { font-family: system-ui, -apple-system, sans-serif; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); border-radius: 12px; padding: 1.5rem; line-height: 1.6; } .smart-card h3 { color: var(--color-primary); margin-top: 0; font-size: 1.1rem; } .smart-card .subtitle { font-style: italic; color: var(--color-muted); margin-bottom: 1.5rem; display: block; } .smart-card .highlight-box { border-left: 4px solid var(--color-primary); background: color-mix(in srgb, var(--color-primary) 8%, transparent); padding: 1rem; border-radius: 0 8px 8px 0; } .smart-card strong { color: var(--color-text); } Reachability in Directed Graph Traversals Understanding how one-way edges change the fundamental nature of graph exploration. The Core Shift In an undirected graph, a traversal from a source vertex naturally discovers its entire connected component. The path can be traversed in both directions. In a directed graph, edges are one-way streets. A traversal from vertex v only discovers vertices that are reachable from v by following the directed edges. It does not guarantee that those discovered vertices can reach back to v .

Directed Reachability vs Undirected Connectivity

.smart-card { font-family: system-ui, -apple-system, sans-serif; background: var(--color-bg); color: var(--color-text); border: 1px solid var(--color-border); border-radius: 12px; padding: 1.5rem; line-height: 1.6; } .smart-card h3 { color: var(--color-primary); margin-top: 0; font-size: 1.1rem; margin-bottom: 1rem; } .smart-card .concept-block { background: color-mix(in srgb, var(--color-muted) 8%, transparent); border-left: 3px solid var(--color-muted); padding: 1rem; border-radius: 0 8px 8px 0; margin-bottom: 1rem; } .smart-card .concept-block.primary { background: color-mix(in srgb, var(--color-primary) 8%, transparent); border-left-color: var(--color-primary); } .smart-card .concept-title { font-weight: bold; display: block; margin-bottom: 0.5rem; font-size: 0.95rem; } .smart-card ul { margin: 0.5rem 0 0 1.2rem; padding: 0; } .smart-card li { margin-bottom: 0.25rem; } Symmetry vs. Asymmetry Undirected Connectivity (Symmetric) If there is a path from v to u, there is inherently a path from u to v . The reachable set from v is exactly the connected component containing v . Directed Reachability (Asymmetric) A directed path from v to u does not imply a path from u to v . We say u is reachable from v . The set of all such vertices is the forward reachable set from v . This set can be strictly smaller than the weakly connected component containing v .

22 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Which of the following statements correctly defines the Strongly Connected Component (SCC) of a vertex v in a directed graph?

Question 2

Level 1: Warm-up

Which of the following statements about the edges produced by a Depth First Search on a simple undirected graph is ALWAYS true?

Question 3

Level 1: Warm-up

Which of the following edge types is mathematically impossible to produce during a Depth First Search on any simple undirected graph?

Question 4

Level 1: Warm-up

During a Depth First Search on a directed graph, the presence of which edge type is both necessary and sufficient to conclude that the graph contains at least one directed cycle?

Question 5

Level 1: Warm-up

A student performs a Depth First Search on a simple undirected graph and reports the following edge classification: Tree edges: 3 Back edges: 2 Forward edges: 1 Cross edges: 0 What is the MINIMUM number of edges that the student MUST have misclassified?

Question 6

Level 1: Warm-up

Which of the following sets of discovery and finish timestamps is mathematically IMPOSSIBLE for a valid Depth First Search on a directed graph?

Question 7

Level 1: Warm-up

Which of the following statements about the intersection of the forward and backward reachable sets from a vertex v in a directed graph is ALWAYS true?

Question 8

Level 1: Warm-up

During a Depth First Search on a simple undirected graph, the edge (u, v) is explored from u and vertex v is found to be already visited. Which of the following must be true about v ?

Question 9

Level 1: Warm-up

During a Depth First Search on a directed graph with 6 vertices and 10 edges, the edge classification yields: Tree edges: 4 Back edges: 3 Forward edges: 1 Cross edges: ? How many Cross edges are there?

Question 10

Level 1: Warm-up

During a Depth First Search on a simple undirected graph with 8 vertices, the algorithm discovers exactly 7 Tree edges. What is the maximum possible number of Back edges that can be generated in this graph?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Graph Traversal: BFS and DFS Notes for GATE DA

Graph Traversal: BFS and DFS notes for GATE DA: 25 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Graph Traversal

What you will master

How directed edges break the symmetry of connectivity.
Using reverse graphs to find strongly connected components.
Classifying edges discovered during Depth First Search.
Accurately tracing traversals on complex visual diagrams.

Reachability in Directed Graph Traversals

Understanding how one-way edges change the fundamental nature of graph exploration.

The Core Shift

In an undirected graph, a traversal from a source vertex naturally discovers its entire connected component. The path can be traversed in both directions.

In a directed graph, edges are one-way streets. A traversal from vertex $v$ only discovers vertices that are reachable from $v$ by following the directed edges. It does not guarantee that those discovered vertices can reach back to $v$ .

Directed Reachability vs Undirected Connectivity

Symmetry vs. Asymmetry

Undirected Connectivity (Symmetric) If there is a path from

v

u

, there is inherently a path from

u

v

. The reachable set from

v

is exactly the connected component containing

v

Directed Reachability (Asymmetric) A directed path from

v

u

does not imply a path from

u

v

We say $u$ is reachable from $v$ .
The set of all such vertices is the forward reachable set from $v$ .
This set can be strictly smaller than the weakly connected component containing $v$ .

The Reverse Graph

Analyzing Backward Reachability

To answer the question "Which vertices can reach $v$ ?", we use the reverse graph, denoted as $G^{R}$ .

G^{R} = (V, E^{R}), where E^{R} = {(u, w) ∣ (w, u) \in E}

Simply flip the direction of every edge.

The Key Property:
A directed path exists from

v

u

G^{R}

if and only if a directed path exists from

u

v

in the original graph

G

Therefore, running a traversal (BFS or DFS) from $v$ in $G^{R}$ yields the exact set of vertices that can reach $v$ in $G$ .

Graph Traversal: BFS and DFS: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming, Data Structures and Algorithms MCQ

Which of the following statements correctly defines the Strongly Connected Component (SCC) of a vertex $v$ in a directed graph?

A.
The union of forward and backward reachable sets from $v$
B.
The intersection of forward and backward reachable sets from $v$
C.
The set of all vertices that can reach $v$
D.
The set of all vertices reachable from $v$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct definition recall question about SCCs.

Step 1: Recall the definition of Strongly Connected Component.

Step 2: An SCC is a maximal set of vertices where every vertex is reachable from every other vertex.

Step 3: For vertex $v$ , this means:

$v$ can reach them (forward reachable)
They can reach $v$ (backward reachable)

Step 4: Therefore, SCC( $v$ ) = forward reachable set $\cap$ backward reachable set.

Answer: The intersection of forward and backward reachable sets from $v$

Question 2 · Programming, Data Structures and Algorithms MCQ

Which of the following statements about the edges produced by a Depth First Search on a simple undirected graph is ALWAYS true?

A.
It can produce Cross edges if the graph is disconnected.
B.
It can produce Forward edges if the graph contains cycles.
C.
It will only produce Tree and Back edges.
D.
It will only produce Tree and Cross edges.

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the fundamental rule of DFS on undirected graphs.

Step 1: Recall the theorem for undirected graphs. When DFS is performed on an undirected graph, every edge is explored in both directions.

Step 2: If an edge $(u, v)$ is explored and $v$ is already visited, $v$ must be an ancestor of $u$ . If $v$ were in a different branch, the edge would have been traversed from $v$ to $u$ earlier, making $u$ a descendant of $v$ .

Step 3: Therefore, any non-tree edge in an undirected graph must be a Back edge. Forward and Cross edges are mathematically impossible.

Step 4: Evaluate the options. Option C correctly states that only Tree and Back edges are produced, regardless of cycles or connectivity.

Answer: It will only produce Tree and Back edges.

Question 3 · Programming, Data Structures and Algorithms MCQ

Which of the following edge types is mathematically impossible to produce during a Depth First Search on any simple undirected graph?

A.
Tree edge
B.
Back edge
C.
Forward edge
D.
Both A and B

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the fundamental rule of DFS on undirected graphs.

Step 1: Recall the theorem for undirected graphs. When DFS explores an edge $(u, v)$ in an undirected graph, the reverse edge $(v, u)$ also exists.

Step 2: If $v$ is already visited when $(u, v)$ is explored, $v$ must be an ancestor of $u$ . If $v$ were in a different branch, the edge would have been traversed from $v$ to $u$ earlier.

Step 3: Therefore, any non-tree edge in an undirected graph must be a Back edge. Forward and Cross edges are mathematically impossible.

Step 4: Evaluate the options. Forward edge is the only correct choice among the single types.

Answer: Forward edge

Question 4 · Programming, Data Structures and Algorithms MCQ

During a Depth First Search on a directed graph, the presence of which edge type is both necessary and sufficient to conclude that the graph contains at least one directed cycle?

A.
Back edge
B.
Tree edge
C.
Forward edge
D.
Cross edge

Correct Answer:

Step-by-Step Solution

Key idea: This is an observation question testing the fundamental relationship between Back edges and cycles.

Step 1: Recall the definition of a Back edge. It is an edge $(u, v)$ where $v$ is an ancestor of $u$ in the DFS tree.

Step 2: If $v$ is an ancestor of $u$ , there is a tree path from $v$ down to $u$ . The Back edge $(u, v)$ completes this into a cycle: $v ⇝ u \to v$ .

Step 3: Conversely, if the graph has a cycle, DFS must produce at least one Back edge. No other edge type guarantees a cycle.

Step 4: Therefore, Back edges are both necessary and sufficient for cycles.

Answer: Back edge

Question 5 · Programming, Data Structures and Algorithms NAT

A student performs a Depth First Search on a simple undirected graph and reports the following edge classification:

Tree edges: 3
Back edges: 2
Forward edges: 1
Cross edges: 0

What is the MINIMUM number of edges that the student MUST have misclassified?

Correct Answer:

1.00

Step-by-Step Solution

Key idea: In an undirected graph, DFS produces ONLY Tree edges and Back edges. Forward and Cross edges are mathematically impossible.

Step 1: Recall the rule for undirected graphs: DFS yields only Tree and Back edges. No Forward or Cross edges can exist.

Step 2: Check the student's report:

Tree edges: 3 (possible ✓)
Back edges: 2 (possible ✓)
Forward edges: 1 (IMPOSSIBLE ✗)
Cross edges: 0 (possible ✓)

Step 3: The Forward edge is impossible in an undirected graph. It must be misclassified (likely as a Tree or Back edge).

Step 4: Count misclassified edges: At least 1 edge (the Forward edge) must be wrong.

Answer: 1

Question 6 · Programming, Data Structures and Algorithms MCQ

Which of the following sets of discovery and finish timestamps is mathematically IMPOSSIBLE for a valid Depth First Search on a directed graph?

A.
$u = [1, 10], v = [2, 5], w = [6, 9]$
B.
$u = [1, 8], v = [3, 6], w = [4, 5]$
C.
$u = [1, 6], v = [4, 9], w = [7, 10]$
D.
$u = [1, 4], v = [6, 9], w = [11, 14]$

Correct Answer:

Step-by-Step Solution

Key idea: The Parenthesis Theorem states that DFS time intervals must be either completely disjoint or strictly nested. Partial overlap is impossible.

Step 1: Check Option A: $u = [1, 10]$ , $v = [2, 5]$ , $w = [6, 9]$ . $v$ and $w$ are nested inside $u$ , and disjoint from each other. Valid.

Step 2: Check Option B: $u = [1, 8]$ , $v = [3, 6]$ , $w = [4, 5]$ . All are strictly nested. Valid.

Step 3: Check Option C: $u = [1, 6]$ , $v = [4, 9]$ . $u$ starts before $v$ , but $u$ finishes before $v$ finishes ( $6 < 9$ ). This is a partial overlap. Invalid.

Step 4: Check Option D: $u = [1, 4]$ , $v = [6, 9]$ , $w = [11, 14]$ . All are completely disjoint. Valid.

Answer: Option C

Question 7 · Programming, Data Structures and Algorithms MCQ

Which of the following statements about the intersection of the forward and backward reachable sets from a vertex $v$ in a directed graph is ALWAYS true?

A.
The intersection is empty if $v$ has no incoming edges.
B.
The intersection contains at least the vertex $v$ itself.
C.
The intersection size is equal to the number of tree edges in the DFS.
D.
The intersection includes all vertices in the weakly connected component of $v$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement truth question about SCC intersection properties.

Step 1: The SCC of $v$ is defined as $R_{f w d} (v) \cap R_{b w d} (v)$ .

Step 2: By definition, $v$ can reach itself (path of length 0), so $v \in R_{f w d} (v)$ .

Step 3: Similarly, $v$ can reach itself, so $v \in R_{b w d} (v)$ .

Step 4: Therefore, $v$ is always in the intersection, meaning the intersection is never empty and contains at least ${v}$ .

Step 5: Evaluate options: A is false (intersection always has $v$ ). B is true. C is false (no relation to tree edges). D is false (weak component can be larger).

Answer: The intersection contains at least the vertex $v$ itself.

Question 8 · Programming, Data Structures and Algorithms MCQ

During a Depth First Search on a simple undirected graph, the edge $(u, v)$ is explored from $u$ and vertex $v$ is found to be already visited. Which of the following must be true about $v$ ?

A.
$v$ is a descendant of $u$ in the DFS tree
B.
$v$ is an ancestor of $u$ in the DFS tree
C.
$v$ belongs to a different DFS tree from $u$
D.
$v$ has a larger discovery time than $u$

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the structural reason why undirected DFS only produces Tree and Back edges.

Step 1: The graph is undirected, so edge $(u, v)$ implies edge $(v, u)$ also exists.

Step 2: Since $v$ is already visited when $(u, v)$ is explored from $u$ , DFS must have reached $v$ earlier.

Step 3: Because the graph is undirected, when DFS first visited $v$ , it would have explored the edge $(v, u)$ . If $u$ was unvisited at that time, DFS would have discovered $u$ as a child of $v$ , making $u$ a descendant of $v$ .

Step 4: This means $v$ is an ancestor of $u$ in the DFS tree. The edge $(u, v)$ is therefore a Back edge.

Step 5: The other options are impossible: $v$ cannot be a descendant (it was visited before $u$ explored this edge), cannot be in a different tree (the undirected edge connects them), and must have a smaller discovery time (visited earlier).

Answer: $v$ is an ancestor of $u$ in the DFS tree

Question 9 · Programming, Data Structures and Algorithms NAT

During a Depth First Search on a directed graph with 6 vertices and 10 edges, the edge classification yields:

Tree edges: 4
Back edges: 3
Forward edges: 1
Cross edges: ?

How many Cross edges are there?

Correct Answer:

2.00

Step-by-Step Solution

Key idea: The total number of edges equals the sum of all edge types.

Step 1: Recall that every edge in a directed graph DFS is classified as exactly one type: Tree, Back, Forward, or Cross.

Step 2: Set up the equation: Total edges = Tree + Back + Forward + Cross

Step 3: Substitute known values: $10 = 4 + 3 + 1 + Cross$

Step 4: Solve for Cross: $Cross = 10 - 4 - 3 - 1 = 2$

Answer: 2

Question 10 · Programming, Data Structures and Algorithms MCQ

During a Depth First Search on a simple undirected graph with 8 vertices, the algorithm discovers exactly 7 Tree edges. What is the maximum possible number of Back edges that can be generated in this graph?

A.
20
B.
21
C.
27
D.
28

Correct Answer:

Step-by-Step Solution

Key idea: In an undirected graph, every edge is either a Tree edge or a Back edge. The maximum number of edges in a simple graph limits the Back edges.

Step 1: Recall that for a simple undirected graph with $V$ vertices, the maximum number of edges is $\frac{V ( V - 1 )}{2}$ .

Step 2: Calculate max edges for $V = 8$ : $\frac{8 \times 7}{2} = 28$ .

Step 3: Recall that every edge is classified as either Tree or Back. So, $Tree + Back = Total Edges$ .

Step 4: We are given $Tree = 7$ . To maximize Back edges, we must maximize Total edges.

Step 5: Max Back edges = Max Total edges - Tree edges = $28 - 7 = 21$ .

Answer: Option B

graph traversal bfs and dfs notes

Chapter Roadmap: Graph Traversal

Chapter Roadmap: Graph Traversal

What you will master

Reachability in Directed Graph Traversals

Reachability in Directed Graph Traversals

The Core Shift

Directed Reachability vs Undirected Connectivity

Symmetry vs. Asymmetry

Try a question

Login to view the complete notes

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: BFS and DFS Notes for GATE DA

Chapter Roadmap: Graph Traversal

Chapter Roadmap: Graph Traversal

What you will master

Reachability in Directed Graph Traversals

Reachability in Directed Graph Traversals

The Core Shift

Directed Reachability vs Undirected Connectivity

Symmetry vs. Asymmetry

The Reverse Graph

Analyzing Backward Reachability

Graph Traversal: BFS and DFS: 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

Step-by-Step Solution

More notes in this unit