Graph Traversals

Overview

The systematic exploration of a graph's vertices and edges is fundamental to the study of algorithms. To solve nearly any problem concerning a graph's structure or properties, we must first possess a methodical procedure for visiting each vertex and examining each edge. Graph traversal algorithms provide this mechanism, offering structured strategies to navigate from a starting vertex to all reachable vertices. These traversals are not merely theoretical exercises; they form the cornerstone upon which a vast number of more complex graph algorithms are built, from finding shortest paths to identifying network flows.

For the GATE examination, a mastery of graph traversal is indispensable. The two primary strategies we shall study, Breadth-First Search (BFS) and Depth-First-Search (DFS), are perennial topics that appear in various forms, both as direct questions and as sub-problems within more intricate scenarios. A deep, analytical understanding of how they operate, the data structures they rely upon (queues and stacks, respectively), and their computational complexity is critical. This chapter is therefore dedicated to a rigorous analysis of these foundational techniques, equipping you with the necessary skills to solve problems related to connectivity, cycle detection, and pathfinding with both accuracy and efficiency.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | BFS and DFS | Core traversal strategies and their applications |

---

Learning Objectives

---

We now turn our attention to BFS and DFS...
## Part 1: BFS and DFS

Introduction

Graph traversal algorithms are fundamental to the study of algorithms, providing systematic methods for visiting the vertices and edges of a graph. They form the basis for solving a vast array of problems, including finding paths, analyzing connectivity, and discovering structural properties of graphs. The two most essential traversal strategies are Breadth-First Search (BFS) and Depth-First Search (DFS).

BFS explores a graph in a level-by-level fashion, examining all vertices at a certain distance from a starting vertex before moving on to vertices further away. This methodical, expanding-wave approach makes it particularly suitable for finding shortest paths in unweighted graphs. In contrast, DFS explores as deeply as possible along each branch before backtracking. This recursive, path-finding nature of DFS lends itself well to problems such as cycle detection, topological sorting, and finding articulation points. A thorough understanding of the mechanics, properties, and applications of both BFS and DFS is indispensable for success in competitive examinations like GATE.

---

Key Concepts

#
## 1. Breadth-First Search (BFS)

The Breadth-First Search algorithm explores a graph by visiting vertices in increasing order of their distance from a source vertex, $s$. It begins at $s$, visits all its immediate neighbors, then all their unvisited neighbors, and so on. This level-by-level exploration is naturally implemented using a queue data structure.

We can visualize the process as an expanding frontier. The source vertex is at level 0. Its direct neighbors are at level 1. The neighbors of level 1 vertices (that have not already been visited) are at level 2, and this continues until all reachable vertices have been visited. The algorithm produces a BFS tree, which contains the shortest paths from the source to all other reachable vertices in an unweighted graph.

The algorithm maintains three key pieces of information for each vertex $u$:

• color[u]: Indicates the state of the vertex (WHITE for unvisited, GRAY for visited but neighbors not fully explored, BLACK for visited and all neighbors explored).


• d[u]: The distance (shortest path length) from the source $s$ to $u$.


• π[u]: The predecessor of $u$ in the BFS tree.

Algorithm Pseudocode:
```
BFS(G, s)
for each vertex u in G.V - {s}
color[u] = WHITE
d[u] = infinity
π[u] = NIL

color[s] = GRAY
d[s] = 0
π[s] = NIL

Q = new Queue()
ENQUEUE(Q, s)

while Q is not empty
u = DEQUEUE(Q)
for each v in G.Adj[u]
if color[v] == WHITE
color[v] = GRAY
d[v] = d[u] + 1
π[v] = u
ENQUEUE(Q, v)
color[u] = BLACK
```

A crucial property of BFS relates to the non-tree edges. In the BFS tree, an edge $(u, v)$ from the original graph is a non-tree edge if it connects two vertices that are not in a parent-child relationship.

This property arises because when we are exploring from vertex $u$, any unvisited neighbor $v$ will be assigned a distance $d[v] = d[u] + 1$. If $v$ was already visited, its distance must be either $d[u]$, $d[u]-1$, or $d[u]+1$ (the last case is not possible if $u$ discovers $v$, so it must have been discovered by another node at level $d[u]$).

Worked Example:

Problem: Perform a BFS traversal on the following unweighted, undirected graph, starting from vertex A. Show the state of the queue and the distances at each step.

A

B

C

D

E

F

Solution:

We initialize distances $d$ to $\infty$ and the queue $Q$ to be empty. Source is A.

Step 1: Initialize source vertex A.
$d[A] = 0$. Enqueue A.
$Q = [A]$

Step 2: Dequeue A. Visit its neighbors B and C.
Dequeue A. $d[B] = d[A] + 1 = 1$, $d[C] = d[A] + 1 = 1$. Enqueue B, then C.
$Q = [B, C]$

Step 3: Dequeue B. Visit its neighbors (A, C, D). A and C are already visited.
Dequeue B. $d[D] = d[B] + 1 = 2$. Enqueue D.
$Q = [C, D]$

Step 4: Dequeue C. Visit its neighbors (A, B, E). A and B are already visited.
Dequeue C. $d[E] = d[C] + 1 = 2$. Enqueue E.
$Q = [D, E]$

Step 5: Dequeue D. Visit its neighbors (B, F). B is visited.
Dequeue D. $d[F] = d[D] + 1 = 3$. Enqueue F.
$Q = [E, F]$

Step 6: Dequeue E. Visit its neighbors (C, F). C is visited. F is GRAY.
Dequeue E. No new white neighbors.
$Q = [F]$

Step 7: Dequeue F. Visit its neighbors (D, E). Both are visited.
Dequeue F. No new white neighbors.
$Q = []$

Answer: The BFS traversal order is A, B, C, D, E, F. The final distances are: $d[A]=0, d[B]=1, d[C]=1, d[D]=2, d[E]=2, d[F]=3$.

---

#
## 2. Depth-First Search (DFS)

Depth-First Search explores a graph by traversing as far as possible along a single path before backtracking. When it reaches a vertex from which it can no longer proceed (i.e., all neighbors have been visited), it backtracks to the previous vertex and explores another unvisited path. This process is naturally implemented using a stack, often implicitly through recursion.

The algorithm maintains the color of each vertex, similar to BFS. Additionally, it computes two timestamps for each vertex $u$:

• d[u]: The discovery time, when $u$ is first visited (becomes GRAY).


• f[u]: The finishing time, when all of $u$'s descendants in the DFS tree have been fully explored ( $u$ becomes BLACK).

Algorithm Pseudocode (Recursive):
```
time = 0

DFS(G)
for each vertex u in G.V
color[u] = WHITE
π[u] = NIL

for each vertex u in G.V
if color[u] == WHITE
DFS-VISIT(G, u)

DFS-VISIT(G, u)
time = time + 1
d[u] = time
color[u] = GRAY

for each v in G.Adj[u]
if color[v] == WHITE
π[v] = u
DFS-VISIT(G, v)

color[u] = BLACK
time = time + 1
f[u] = time
```

#
### Edge Classification in DFS

A significant feature of DFS is its ability to classify the edges of the graph based on the traversal. This classification is critical for many advanced algorithms. For an edge $(u, v)$:

• Tree Edge: $v$ was first discovered by exploring edge $(u, v)$. These edges form the DFS forest.
• Back Edge: $v$ is an ancestor of $u$ in the DFS tree. Back edges are a key indicator of cycles in a graph.
• Forward Edge: $v$ is a proper descendant of $u$ in the DFS tree.
• Cross Edge: All other edges. They connect vertices in different subtrees of the DFS forest, or two vertices where neither is an ancestor of the other.

Tree Edge



Back Edge

Forward Edge

Cross Edge

#
## 3. Applications and Advanced Concepts

#
### Finding Connected Components

For an undirected graph, both BFS and DFS can be used to find its connected components. The main procedure involves iterating through all vertices. If a vertex has not been visited, a new traversal (either BFS or DFS) is started from it. This traversal will visit all vertices in one connected component. The number of times a new traversal is initiated is the number of connected components.

#
### Finding Articulation Points

An articulation point (or cut vertex) is a vertex whose removal increases the number of connected components of a graph. DFS provides an efficient way to find all articulation points. The logic relies on identifying if a subtree rooted at a vertex `v` has a "back-up" connection to an ancestor of `v`'s parent, `u`.

The conditions for a vertex $u$ to be an articulation point are:

$u$ is the root of the DFS tree: The root is an articulation point if and only if it has two or more children.

$u$ is not the root: A non-root vertex $u$ is an articulation point if and only if it has at least one child $v$ such that no vertex in the subtree rooted at $v$ (including $v$ itself) has a back edge to a proper ancestor of $u$.

A leaf of a DFS tree (a vertex with no children in the tree) can never be an articulation point in a connected graph with more than two vertices, as its removal does not disconnect its parent from the rest of the graph.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A BFS traversal is performed on an unweighted, undirected connected graph $G$ starting from a source vertex $s$. Let $(u, v)$ be an edge in $G$ that is NOT part of the resulting BFS tree. Which of the following statements is ALWAYS true about the distances $d(s,u)$ and $d(s,v)$?" options=["$d(s,u) = d(s,v)$","$d(s,u) = d(s,v) + 1$","$|d(s,u) - d(s,v)| \le 1$","No conclusion can be drawn"] answer="|d(s,u) - d(s,v)| \le 1" hint="Recall the property of non-tree edges in a BFS traversal. Consider the levels of vertices u and v." solution="In a BFS traversal of an undirected graph, any edge $(u, v)$ connects vertices that are at most one level apart. Let $d(s, u)$ be the level of vertex $u$. When the algorithm explores vertex $u$, it discovers all its neighbors. If neighbor $v$ is unvisited, it is placed at level $d(s,u)+1$. If $v$ is already visited, its level must be $d(s,u)$ or $d(s,u)-1$. Therefore, for any edge $(u, v)$, the level difference is at most 1.

"
:::

:::question type="NAT" question="Consider an undirected graph represented by the adjacency list: A: [B, C], B: [A, D, E], C: [A, E], D: [B], E: [B, C]. A DFS traversal is started at vertex A. The vertices are pushed onto the stack in alphabetical order. The sequence of popped vertices from the recursion stack represents one possible DFS traversal order. What is the 4th vertex in this sequence?" answer="D" hint="Simulate the recursive DFS. The popped sequence corresponds to the order in which vertices finish their exploration (are colored BLACK)." solution="Step 1: Start DFS at A. Push A to stack. Stack: [A].
Step 2: Explore neighbors of A (B, C). Choose B first (alphabetical). Push B. Stack: [A, B].
Step 3: Explore neighbors of B (A, D, E). A is visited. Choose D. Push D. Stack: [A, B, D].
Step 4: Explore neighbors of D (B). B is visited. D has no more unvisited neighbors. Pop D. Popped sequence: [D]. Stack: [A, B].
Step 5: Backtrack to B. Explore next neighbor E. Push E. Stack: [A, B, E].
Step 6: Explore neighbors of E (B, C). B is visited. C is unvisited (neighbor of A, but not yet explored from this path). Push C. Stack: [A, B, E, C].
Step 7: Explore neighbors of C (A, E). Both are visited. Pop C. Popped sequence: [D, C]. Stack: [A, B, E].
Step 8: Backtrack to E. All neighbors visited. Pop E. Popped sequence: [D, C, E]. Stack: [A, B].
Step 9: Backtrack to B. All neighbors visited. Pop B. Popped sequence: [D, C, E, B]. Stack: [A].
Step 10: Backtrack to A. All neighbors visited. Pop A. Popped sequence: [D, C, E, B, A].

The order of finishing (popping) is D, C, E, B, A. The 4th vertex in this sequence is B.
Wait, the question asks for the traversal order, which is the discovery order (pre-order traversal of the DFS tree). Let's re-trace for discovery order.

Correct Interpretation: Traversal order is the order of first visit.

Visit A.

Visit B (from A).

Visit D (from B).

Visit E (from B, after returning from D).

Visit C (from E).

Traversal order: A, B, D, E, C. The 4th vertex is E.

Let's re-read the question carefully: "The sequence of popped vertices from the recursion stack". This is the post-order traversal of the DFS tree. My first solution was correct based on this wording.
Popped sequence (finishing order): D, C, E, B, A.
The 4th vertex in this sequence is B.

Let's consider the standard definition of "DFS traversal order", which is pre-order.

Visit A. Order: [A]

From A, go to B. Order: [A, B]

From B, go to D. Order: [A, B, D]

Backtrack from D. From B, go to E. Order: [A, B, D, E]

From E, go to C. Order: [A, B, D, E, C]

The 4th vertex visited is E.

The question is slightly ambiguous. "Sequence of popped vertices" usually means post-order. Let's assume the most standard interpretation: pre-order traversal.

Re-Solution (Pre-order):
Step 1: Start at A. Traversal: [A]. Stack: [A].
Step 2: Push neighbor B. Traversal: [A, B]. Stack: [A, B].
Step 3: Push neighbor D of B. Traversal: [A, B, D]. Stack: [A, B, D].
Step 4: D has no new neighbors. Backtrack. Pop D.
Step 5: From B, push neighbor E. Traversal: [A, B, D, E]. Stack: [A, B, E].
Step 6: From E, push neighbor C. Traversal: [A, B, D, E, C]. Stack: [A, B, E, C].
The 4th vertex visited is E.

Let's assume the question meant "popped" as in "dequeued" from a queue in an iterative implementation, which is not standard for DFS. Given the ambiguity, let's stick to the finishing time order, as "popped from recursion stack" has a precise meaning.
Sequence of finished vertices: D, C, E, B, A. The 4th is B.

Let's assume the question is flawed and means discovery order. Then it's E.
Let's assume it means the order vertices are put ONTO the stack. A, B, D, E, C. 4th is E.
Let's assume it means the order vertices are popped OFF the stack. D, C, E, B, A. 4th is B.

Let's provide the answer for the post-order traversal as it matches the phrasing "popped vertices".
Final trace of finishing times:

• DFS(A) -> DFS(B) -> DFS(D). D has no unvisited neighbors. D finishes.


• DFS(B) -> DFS(E). E has neighbor C.


• DFS(E) -> DFS(C). C has no unvisited neighbors. C finishes.


• E has no more unvisited neighbors. E finishes.


• B has no more unvisited neighbors. B finishes.


• A has no more unvisited neighbors. A finishes.

Finishing order: D, C, E, B, A. The 4th vertex to finish is B.

Let's re-write the question to be less ambiguous for my notes.
New Question: A DFS traversal is started at vertex A. The neighbors of any vertex are visited in alphabetical order. What is the 4th vertex to be marked as finished (colored BLACK)?
Answer: B.
Solution:
Step 1: Call `DFS-VISIT(A)`.
Step 2: From A, call `DFS-VISIT(B)`.
Step 3: From B, call `DFS-VISIT(D)`.
Step 4: D's only other neighbor B is already GRAY. D has no unvisited neighbors. D is marked BLACK. Finish 1: D.
Step 5: Return to B. Visit next neighbor E. Call `DFS-VISIT(E)`.
Step 6: From E, visit neighbor C. Call `DFS-VISIT(C)`.
Step 7: C's neighbors A and E are GRAY. C is marked BLACK. Finish 2: C.
Step 8: Return to E. All neighbors visited. E is marked BLACK. Finish 3: E.
Step 9: Return to B. All neighbors visited. B is marked BLACK. Finish 4: B.
Step 10: Return to A. All neighbors visited. A is marked BLACK. Finish 5: A.
The 4th vertex to be marked as finished is B.

This is a better question. Let's make one more.
NAT Question: In an undirected graph with 50 vertices, a DFS traversal results in a DFS forest containing 38 edges. How many connected components does the graph have?
Answer: 12
Hint: Use the formula relating vertices, edges in a spanning forest, and the number of components.
Solution:
Let $V$ be the number of vertices, $E_f$ be the number of edges in the DFS forest, and $k$ be the number of connected components. The formula is $E_f = V - k$.
We are given $V = 50$ and $E_f = 38$.

The graph has 12 connected components.
"
:::

:::question type="MSQ" question="Let $T$ be a DFS tree of a connected undirected graph $G$. Which of the following statements is/are necessarily TRUE?" options=["The root of $T$ is an articulation point if it has more than one child.","Every leaf of $T$ is not an articulation point.","An edge $(u,v)$ in $G$ that is not in $T$ must be a back edge, where one of $u$ or $v$ is an ancestor of the other in $T$.","DFS finds the path with the maximum number of edges between any two vertices."] answer="A,B,C" hint="Analyze the properties of DFS trees, articulation points, and edge classifications in undirected graphs." solution="

• A: The root of $T$ is an articulation point if it has more than one child. This is the standard condition for the root of a DFS tree to be a cut vertex. If the root has two or more children, removing the root separates the subtrees rooted at these children into different components. This statement is TRUE.


• B: Every leaf of $T$ is not an articulation point. A leaf in the DFS tree has no descendants in the tree. Removing a leaf node (and its single incident tree edge) from a connected graph with $|V|>2$ cannot disconnect the graph. Its parent remains connected to the rest of the graph. This statement is TRUE.


• C: An edge $(u,v)$ in $G$ that is not in $T$ must be a back edge... In an undirected graph, all non-tree edges are back edges. This means for a non-tree edge $(u,v)$, one vertex must be an ancestor of the other in the DFS tree. This statement is TRUE.


• D: DFS finds the path with the maximum number of edges... DFS does not guarantee finding either the shortest or the longest path. It simply finds a path based on its exploration strategy. This statement is FALSE.

"
:::

:::question type="NAT" question="A complete binary tree has 15 nodes, labeled 1 to 15 in a level-order fashion (root is 1, its children are 2 and 3, etc.). Let $S_{BFS}$ be the set of the first 5 nodes visited in a BFS starting from the root. Let $S_{DFS}$ be the set of the first 5 nodes visited in a DFS starting from the root (assume left child is visited before right child). Calculate the value of $|S_{BFS} \cup S_{DFS}| - |S_{BFS} \cap S_{DFS}|$. " answer="4" hint="This expression is equivalent to calculating the size of the symmetric difference: $|S_{BFS} \triangle S_{DFS}|$. First, find the two sets by tracing the traversals." solution="
Step 1: Determine the set $S_{BFS}$.
BFS explores level by level.
Level 0: 1
Level 1: 2, 3
Level 2: 4, 5, 6, 7
The first 5 nodes visited by BFS are {1, 2, 3, 4, 5}.
So, $S_{BFS} = \{1, 2, 3, 4, 5\}$.

Step 2: Determine the set $S_{DFS}$.
DFS goes deep down the left subtree first.
1 -> 2 (left child of 1)
2 -> 4 (left child of 2)
4 -> 8 (left child of 4)
8 -> (no children, backtrack)
4 -> 9 (right child of 4)
The first 5 nodes visited by DFS are {1, 2, 4, 8, 9}.
So, $S_{DFS} = \{1, 2, 4, 8, 9\}$.

Step 3: Calculate the required value.
We need to find $|S_{BFS} \cup S_{DFS}| - |S_{BFS} \cap S_{DFS}|$.
$S_{BFS} \cup S_{DFS} = \{1, 2, 3, 4, 5, 8, 9\}$. So, $|S_{BFS} \cup S_{DFS}| = 7$.
$S_{BFS} \cap S_{DFS} = \{1, 2, 4\}$. So, $|S_{BFS} \cap S_{DFS}| = 3$.
The value is $7 - 3 = 4$.

Alternatively, the symmetric difference is the set of elements in either set, but not in their intersection.
$S_{BFS} \setminus S_{DFS} = \{3, 5\}$
$S_{DFS} \setminus S_{BFS} = \{8, 9\}$
$|S_{BFS} \triangle S_{DFS}| = |\{3, 5, 8, 9\}| = 4$.

Result: 4
"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Let $T_{BFS}$ and $T_{DFS}$ be the breadth-first and depth-first search trees, respectively, for a given connected, unweighted graph $G$ starting from the same vertex $v$. Let $h(T)$ denote the height of a tree $T$. Which of the following statements is always true?" options=["$h(T_{BFS}) \leq h(T_{DFS})$","$h(T_{BFS}) \geq h(T_{DFS})$","$h(T_{BFS}) = h(T_{DFS})$","No definite relationship can be established between $h(T_{BFS})$ and $h(T_{DFS})$"] answer="A" hint="Consider the fundamental property of BFS concerning path lengths from the source vertex. How does this relate to the height of the resulting tree?" solution="The height of a tree rooted at $v$ is the length of the longest path from $v$ to any leaf node.

In a BFS traversal starting from vertex $v$, the path from $v$ to any other vertex $u$ in the BFS tree $T_{BFS}$ corresponds to the shortest path (in terms of the number of edges) from $v$ to $u$ in the original graph $G$. Therefore, the height of the BFS tree, $h(T_{BFS})$, is the length of the longest shortest path from $v$ to any other vertex in the graph. This is also known as the eccentricity of vertex $v$.

A DFS traversal, on the other hand, explores as deeply as possible. The path from $v$ to a vertex $u$ in the DFS tree $T_{DFS}$ is a simple path, but it is not guaranteed to be the shortest path. It is possible for DFS to take a long, winding path to a vertex that is actually very close to the source.

Consequently, the length of the longest path in a DFS tree can be greater than or equal to the length of the longest shortest path from the source. It can never be shorter, because the BFS height is, by definition, the minimum possible height for any spanning tree that preserves shortest path distances from the root.

Thus, we can definitively conclude that $h(T_{BFS}) \leq h(T_{DFS})$.
"
:::

:::question type="NAT" question="Consider a directed graph $G=(V, E)$ where $V = \{1, 2, 3, 4, 5, 6\}$ and the adjacency list is given as:
1: [2, 3]
2: [4]
3: [4, 5]
4: [6]
5: [6]
6: [3]
A Depth First Search is performed starting at vertex 1. The algorithm explores neighbors in the order they appear in the adjacency list. What is the number of back edges found during this traversal?" answer="1" hint="Perform a DFS traversal, keeping track of the recursion stack (or the set of current ancestors). An edge $(u, v)$ is a back edge if $v$ is currently in the recursion stack when the edge is explored from $u$." solution="We perform a DFS starting from vertex 1, exploring neighbors in the given order. We will maintain the recursion stack (the set of active vertices in the current path).

DFS(1):

- Push 1 onto stack. Stack: `[1]`
- Explore neighbor 2.

DFS(2):

- Push 2 onto stack. Stack: `[1, 2]`
- Explore neighbor 4.

DFS(4):

- Push 4 onto stack. Stack: `[1, 2, 4]`
- Explore neighbor 6.

DFS(6):

- Push 6 onto stack. Stack: `[1, 2, 4, 6]`
- Explore neighbor 3.

DFS(3):

- Push 3 onto stack. Stack: `[1, 2, 4, 6, 3]`
- Explore neighbor 4. Vertex 4 is already visited. Is it an ancestor? We check the stack. Yes, 4 is in the stack `[1, 2, 4, 6, 3]`. So, the edge $(3, 4)$ is a Cross Edge. (It goes from one subtree to another, specifically from the subtree rooted at 3 to the subtree rooted at 4, but 4 is already finished in the context of the path from 2). Correction: Let's be more precise. When we are at 3, the path is 1-2-4-6-3. Vertex 4 is visited and finished in the branch 1-2-4. So (3,4) is a cross edge.
- Explore neighbor 5.

DFS(5):

- Push 5 onto stack. Stack: `[1, 2, 4, 6, 3, 5]`
- Explore neighbor 6. Vertex 6 is already visited. Is it an ancestor? Yes, 6 is in the stack `[1, 2, 4, 6, 3, 5]`. Therefore, the edge $(5, 6)$ is a Cross Edge as well. (6 is not a direct ancestor of 5 in the path 1-2-4-6-3-5, but it is an ancestor of 3, which is an ancestor of 5).
- No more neighbors for 5. Pop 5. Stack: `[1, 2, 4, 6, 3]`

(Back at DFS(3)) No more neighbors for 3. Pop 3. Stack: `[1, 2, 4, 6]`

(Back at DFS(6)) The edge to explore is $(6, 3)$. Vertex 3 is already visited. Is it an ancestor of 6? We check the stack `[1, 2, 4, 6]`. No, 3 is not on the stack. In fact, 3 was just finished. Wait, let's retrace.

- The path is 1 -> 2 -> 4 -> 6. Now at 6, explore neighbor 3. Vertex 3 is unvisited.
- DFS(3):
- Push 3. Stack: `[1, 2, 4, 6, 3]`
- Explore neighbor 4. Vertex 4 is visited and is an ancestor (on the stack). This is a Back Edge. Edge $(3,4)$.
- Let's restart the trace carefully.

Correct Trace:

• Start DFS(1). Path: [1]. Visited: {1}.


• Explore 1->2. Call DFS(2). Path: [1, 2]. Visited: {1, 2}.


• Explore 2->4. Call DFS(4). Path: [1, 2, 4]. Visited: {1, 2, 4}.


• Explore 4->6. Call DFS(6). Path: [1, 2, 4, 6]. Visited: {1, 2, 4, 6}.


• Explore 6->3. Call DFS(3). Path: [1, 2, 4, 6, 3]. Visited: {1, 2, 4, 6, 3}.


• At 3, explore 3->4. Vertex 4 is visited. Is 4 an ancestor of 3? Yes, it is in the current path `[1, 2, 4, 6, 3]`. So, (3, 4) is a Back Edge.


• At 3, explore 3->5. Call DFS(5). Path: [1, 2, 4, 6, 3, 5]. Visited: {1, 2, 4, 6, 3, 5}.


• At 5, explore 5->6. Vertex 6 is visited. Is 6 an ancestor of 5? Yes, it is in the current path. So, (5, 6) is a Back Edge.


• DFS(5) finishes. Pop 5.


• DFS(3) finishes. Pop 3.


• DFS(6) finishes. Pop 6.


• DFS(4) finishes. Pop 4.


• DFS(2) finishes. Pop 2.


• Back at 1, explore 1->3. Vertex 3 is already visited. It is not an ancestor. This is a cross edge.


• DFS(1) finishes. Pop 1.

There seems to be a mistake in my manual trace. Let's use discovery/finish times and the formal definition. A back edge $(u, v)$ is one where $v$ is an ancestor of $u$. This means $v$ is currently in the recursion stack when we explore from $u$.

Let's trace again, very carefully.

`DFS(1)`: `visiting[1] = true`, `recursion_stack[1] = true`.

`DFS(2)` from 1: `visiting[2] = true`, `recursion_stack[2] = true`.

`DFS(4)` from 2: `visiting[4] = true`, `recursion_stack[4] = true`.

`DFS(6)` from 4: `visiting[6] = true`, `recursion_stack[6] = true`.

`DFS(3)` from 6: `visiting[3] = true`, `recursion_stack[3] = true`.

At 3, check edge (3, 4). `visiting[4]` is true. `recursion_stack[4]` is true. This means 4 is an ancestor of 3. This is a back edge. (Cycle: 4->6->3->4).

At 3, check edge (3, 5). `visiting[5]` is false. Call `DFS(5)`.

`DFS(5)` from 3: `visiting[5] = true`, `recursion_stack[5] = true`.

At 5, check edge (5, 6). `visiting[6]` is true. `recursion_stack[6]` is true. This means 6 is an ancestor of 5. This is a back edge. (Cycle: 6->3->5->6).

`DFS(5)` finishes. `recursion_stack[5] = false`.

`DFS(3)` finishes. `recursion_stack[3] = false`.

`DFS(6)` finishes. `recursion_stack[6] = false`.

`DFS(4)` finishes. `recursion_stack[4] = false`.

`DFS(2)` finishes. `recursion_stack[2] = false`.

At 1, check edge (1, 3). `visiting[3]` is true. `recursion_stack[3]` is false. This is a cross or forward edge.

16.`DFS(1)` finishes. `recursion_stack[1] = false`.

My trace identified two back edges: (3,4) and (5,6). Let me re-read the question. "What is the number of back edges found". It's 2. Let me check the graph again.
1->2, 1->3
2->4
3->4, 3->5
4->6
5->6
6->3
Okay, let's trace the cycle 6->3->4->6. Yes.
And 6->3->5->6. Yes.

Wait, is there an ambiguity in the problem? Let's check the first cycle again: 4->6->3->4. This is a cycle. Edge (3,4) is a back edge.
Second cycle: 6->3->5->6. This is a cycle. Edge (5,6) is a back edge.

Why would the answer be 1? Let me think. Maybe I misread the graph. No, the graph is clear. Maybe the order of exploration matters more than I thought.

Start at 1. Go to 2.

At 2. Go to 4.

At 4. Go to 6.

At 6. Go to 3.

At 3. Go to 4. Vertex 4 is an ancestor. Back Edge (3,4).

At 3. Go to 5.

At 5. Go to 6. Vertex 6 is an ancestor. Back Edge (5,6).

Finish 5. Finish 3. Finish 6. Finish 4. Finish 2.

At 1. Go to 3. Vertex 3 is visited. Not an ancestor. Cross edge.

Finish 1.

This trace consistently gives 2 back edges. Let me try a different exploration order from 1. What if we go to 3 first?

Start at 1. Go to 3.

At 3. Go to 4.

At 4. Go to 6.

At 6. Go to 3. Vertex 3 is an ancestor. Back Edge (6,3).

Finish 6. Finish 4. Finish 3.

At 1. Go to 2.

At 2. Go to 4. Vertex 4 is visited. Not an ancestor. Cross Edge.

Finish 2. Finish 1.

In this order, there is only one back edge.

The question specifies the order: "The algorithm explores neighbors in the order they appear in the adjacency list."
So my first trace is the only correct one.
1: [2, 3] -> Go to 2 first.
My first trace yields 2 back edges. Is it possible my definition of back edge is wrong?
A back edge (u, v) is an edge where v is an ancestor of u in the DFS tree. My trace seems to follow this.
Path: 1->2->4->6->3. Ancestors of 3 are {6, 4, 2, 1}. Edge (3,4) points to ancestor 4. It's a back edge.
Path: 1->2->4->6->3->5. Ancestors of 5 are {3, 6, 4, 2, 1}. Edge (5,6) points to ancestor 6. It's a back edge.

There are definitely two back edges. Why would I set the answer to 1? Let me reconsider the graph.
Cycle 1: 4 -> 6 -> 3 -> 4
Cycle 2: 3 -> 5 -> 6 -> 3 (This is not a cycle, edge is 5->6, then 6->3)
Let's see the cycles.
C1: 3 -> 4 -> 6 -> 3
C2: 3 -> 5 -> 6 -> 3
These are two distinct cycles. A DFS must find a back edge for each fundamental cycle it traverses.
It seems my analysis leading to 2 is correct. Maybe I should create a simpler question or graph where the answer is unambiguously 1.

Let's modify the graph.
1: [2]
2: [3]
3: [4, 5]
4: [2]
5: [6]
6: []
Start at 1.

DFS(1) -> DFS(2) -> DFS(3) -> DFS(4).

At 4, explore 4->2. Vertex 2 is visited and is an ancestor of 4 (path 1->2->3->4). So (4,2) is a Back Edge.

Return from 4. At 3, explore 3->5.

DFS(5) -> DFS(6).

Finish 6, 5, 3, 2, 1.

This gives exactly one back edge. This is a much cleaner question. I will use this modified graph.

New Graph for NAT question:
V = {1, 2, 3, 4, 5, 6}
Adj List:
1: [2]
2: [3]
3: [4, 5]
4: [2]
5: [6]
6: []
Start DFS at 1. Neighbors explored in order.
Solution Trace:

DFS(1): Path: `[1]`.

Explore 1->2. Call DFS(2). Path: `[1, 2]`.

Explore 2->3. Call DFS(3). Path: `[1, 2, 3]`.

Explore 3->4 (first in list). Call DFS(4). Path: `[1, 2, 3, 4]`.

At 4, explore 4->2. Vertex 2 is visited. Is 2 an ancestor of 4? Yes, it is in the current recursion path `[1, 2, 3, 4]`. Therefore, the edge (4, 2) is a back edge.

`DFS(4)` finishes.

Back at 3. Explore 3->5. Call DFS(5). Path: `[1, 2, 3, 5]`.

Explore 5->6. Call DFS(6). Path: `[1, 2, 3, 5, 6]`.

`DFS(6)` finishes.

`DFS(5)` finishes.

`DFS(3)` finishes.

`DFS(2)` finishes.

`DFS(1)` finishes.

During the entire traversal, only one back edge, (4, 2), was identified. The answer is 1. This is a good, unambiguous NAT question.
Final Answer: 1.

:::

:::question type="MSQ" question="Which of the following applications can be efficiently solved using Breadth-First Search (BFS)?" options=["Finding the shortest path between two nodes in an unweighted graph.","Detecting a cycle in a directed graph.","Finding the connected components of an undirected graph.","Computing a topological sort of a Directed Acyclic Graph (DAG)."] answer="A,C" hint="BFS explores level by level. Consider which problems benefit from this property. Also, think about what a basic traversal can accomplish regardless of its specific order." solution="Let us analyze each option:

A. Finding the shortest path between two nodes in an unweighted graph: This is a canonical application of BFS. Because BFS explores the graph layer by layer from the source, the first time it reaches a target node, it is guaranteed to have found a path with the minimum number of edges. This statement is correct.

B. Detecting a cycle in a directed graph: While BFS can be adapted to detect cycles, DFS is far more natural and efficient for this task, especially due to its ability to identify back edges. A cycle is detected in BFS if we visit a node that is already in the queue, which is a more complex condition to check than the DFS back edge property. While possible, it's not considered a primary or efficient application compared to DFS.

C. Finding the connected components of an undirected graph: Any graph traversal algorithm, including BFS, can be used to find connected components. We can iterate through all vertices. If a vertex has not been visited, we start a BFS from it. This BFS will visit all vertices in its connected component. We repeat this process until all vertices are visited, identifying one component per BFS initiation. This statement is correct.

D. Computing a topological sort of a Directed Acyclic Graph (DAG): Topological sorting is fundamentally based on the ordering of vertices provided by Depth-First Search finish times. An alternative algorithm (Kahn's algorithm) uses in-degrees and a queue, which is structurally similar to BFS, but it is a distinct algorithm. Standard BFS itself does not produce a topological sort.

Therefore, the applications efficiently solved using BFS are finding the shortest path in unweighted graphs and finding connected components.
"
:::
I need one more question. I've done MCQ and NAT. I'll do another MCQ. MSQ is not a standard GATE type, so I will replace the MSQ with another MCQ.

New Question 3 (MCQ):
This will be about running time on a complete graph.
"What is the time complexity of running Breadth-First Search (BFS) on a complete graph $K_n$ with $n$ vertices, represented using an adjacency matrix?"
Options:
A) $O(n)$
B) $O(n \log n)$
C) $O(n+E)$ where $E$ is the number of edges
D) $O(n^2)$

This is a good question.
Number of vertices $V=n$.
In a complete graph, number of edges $E = \binom{n}{2} = \frac{n(n-1)}{2} = O(n^2)$.
The graph is represented by an adjacency matrix.
The general time complexity for BFS on an adjacency matrix is $O(V^2) = O(n^2)$.
Even if we use the $O(V+E)$ formula for adjacency lists, for a complete graph this becomes $O(n + n^2) = O(n^2)$.
So in both cases, the answer is $O(n^2)$. Option D is correct.

New Question 4 (NAT):
Let's do a question on the maximum size of the queue in a BFS.
"A Breadth-First Search is executed on a complete bipartite graph $K_{3,5}$, starting from a vertex in the partition of size 3. What is the maximum number of vertices ever present in the queue at any one time during the execution of the traversal?"
Let the partitions be $U$ with $|U|=3$ and $V$ with $|V|=5$.
Start at a vertex $u_1 \in U$.

Queue: `[u1]`. (Size 1)

Dequeue `u1`. Enqueue all its neighbors. All vertices in $V$ are neighbors.

Queue: `[v1, v2, v3, v4, v5]`. (Size 5)

Dequeue `v1`. Enqueue its neighbors (all of $U$). `u1` is already visited. Enqueue `u2`, `u3`.

Queue: `[v2, v3, v4, v5, u2, u3]`. (Size 6)

Dequeue `v2`. Its neighbors are in $U$, all visited. Queue size decreases.

The maximum size seems to be 6. Let me re-verify.

• Q: `[u1]` (size 1)


• Dequeue u1. Enqueue v1, v2, v3, v4, v5.


• Q: `[v1, v2, v3, v4, v5]` (size 5). Max so far = 5.


• Dequeue v1. Its neighbors are u1, u2, u3. u1 is visited. Enqueue u2, u3.


• Q: `[v2, v3, v4, v5, u2, u3]` (size 6). Max so far = 6.


• Dequeue v2. Neighbors u1, u2, u3 are all visited.


• Q: `[v3, v4, v5, u2, u3]` (size 5).


• Dequeue v3. Neighbors u1, u2, u3 are all visited.


• Q: `[v4, v5, u2, u3]` (size 4).


• Dequeue v4. Neighbors u1, u2, u3 are all visited.


• Q: `[v5, u2, u3]` (size 3).


• Dequeue v5. Neighbors u1, u2, u3 are all visited.


• Q: `[u2, u3]` (size 2).


• Dequeue u2. All its neighbors in V are visited.


• Q: `[u3]` (size 1).


• Dequeue u3. All its neighbors in V are visited.


• Q: `[]` (size 0).

The maximum size was 6.

What if we started in the partition of size 5?
Start at $v_1 \in V$.

Q: `[v1]` (size 1)

Dequeue v1. Enqueue all its neighbors in U.

Q: `[u1, u2, u3]` (size 3). Max so far = 3.

Dequeue u1. Enqueue its neighbors in V (v1 is visited). Enqueue v2, v3, v4, v5.

Q: `[u2, u3, v2, v3, v4, v5]` (size 6). Max so far = 6.

The max size is 6 regardless of starting partition.

What if the graph was $K_{m,n}$? Start in partition $m$.

Q has 1 element.

Dequeue it. Enqueue all $n$ neighbors. Q size = $n$.

Dequeue one of the $n$. Enqueue its $m-1$ unvisited neighbors. Q size = $(n-1) + (m-1) = n+m-2$.

This seems complicated. Let's stick to the numbers.
For $K_{3,5}$:
Start in partition of 3.
Q: `[u1]`
deQ u1, enQ v1,v2,v3,v4,v5. Q: `[v1,v2,v3,v4,v5]`. Size 5.
deQ v1, enQ u2,u3. Q: `[v2,v3,v4,v5,u2,u3]`. Size 6.
deQ v2, neighbors u1,u2,u3 visited. Q: `[v3,v4,v5,u2,u3]`. Size 5.
...
The max size is 6.

Let's check the other way again. Start in partition of 5.
Q: `[v1]`
deQ v1, enQ u1,u2,u3. Q: `[u1,u2,u3]`. Size 3.
deQ u1, enQ v2,v3,v4,v5. Q: `[u2,u3,v2,v3,v4,v5]`. Size 6.
deQ u2, neighbors v1..v5 all visited. Q: `[u3,v2,v3,v4,v5]`. Size 5.
...
The max size is 6.

The question states "starting from a vertex in the partition of size 3". So my first trace is the one to use.
The maximum size is indeed 6.
Answer = 6. This is a good NAT question. It tests understanding of the BFS mechanism on a standard graph structure.

I will use these four questions:

MCQ: Comparing BFS/DFS tree heights.

NAT: Finding back edges in a DFS traversal. (Using the cleaned-up graph)

MCQ: Time complexity on a complete graph with adjacency matrix.

NAT: Max queue size in BFS on a complete bipartite graph.

This set provides a good mix of conceptual and procedural knowledge testing. Now I will write the final output. I will replace the MSQ I drafted with the new MCQ.
The question types will be MCQ, NAT, MCQ, NAT. That's 4 questions as requested.
The LaTeX and formatting will be double-checked.
The "What's Next" section seems straightforward to write based on my earlier plan.
All looks good. I'm ready to generate the final response.