GATE CSE · Algorithms

Graph Traversal Practice Questions

Master topic for Graph Traversal. Includes Breadth First Search (BFS), Depth First Search (DFS), Topological Sorting.

152 questions · 0 PYQs · 20 AI practice · GATE CSE 2027

📘 Graph Traversal – Concept Summary

### 1. Foundational Definitions and Taxonomy In the architecture of graph algorithms, traversal is the atomic operation. It is the fundamental mechanism for exploring the connectivity and structure of a system. For the GATE candidate, graph traversal is a high-yield topic that bridges basic data structures with advanced algorithmic strategies like Dynamic Programming and Network Flow. - **Graph Traversal**: The systematic process of visiting all vertices and edges in a graph $G(V, E)$. - **Breadth-First Search (BFS)**: A level-order exploration strategy that visits all immediate neighbors before moving deeper. - **Depth-First Search (DFS)**: A backtracking-based strategy that explores as far as possible along a branch before retreating. - **Visited Array**: A mandatory Boolean array of size $V$ used to track states. It is the primary mechanism to prevent infinite loops in cyclic graphs. **Traversal Contextual Comparison:** | Feature | Traversal in Trees | Traversal in Graphs | | :--- | :--- | :--- | | **Connectivity** | Always connected | Can be disconnected; requires multiple restarts | | **Cycle Risk** | Acyclic; traversal is straightforward | Cyclic; requires a Visited Array to prevent loops | | **Path Uniqueness** | Single unique path between nodes | Multiple paths possible; strategy dictates path found | > **The Strategic Role of State Management**: Unlike trees, where the parent-child hierarchy prevents re-visitation, graphs contain cycles. The Visited Array is not optional; it is the state manager that ensures each vertex is processed exactly once, transforming a potentially infinite search space into a finite $O(V+E)$ operation. ### 2. Core Philosophical Intuition The choice between "layering" and "diving" dictates the efficiency of your final solution. - **BFS: "Ripples in a Pond"**: BFS expands outward from the source in concentric circles. This layer-by-layer expansion ensures that when a vertex is first reached, it is via the path with the minimum number of edges. It prioritizes the "breadth" of the search frontier. - **DFS: "The Maze Solver"**: DFS mimics an explorer in a dark maze with a ball of string. The algorithm dives deep into one path until it hits a "dead end" (a leaf or a previously visited node), then uses the string to backtrack and explore the next available branch. - **Reachability**: Both algorithms are fundamentally tools to determine reachability. By initiating a traversal from vertex $u$, any vertex $v$ marked "visited" at the end is reachable from $u$. This logic forms the basis for identifying Connected Components. ### 3. Key Behavioral Properties The divergent behaviors of BFS and DFS are consequences of their underlying data structures. - **BFS (Queue - FIFO)**: Neighbors are enqueued and processed in the order they were discovered. This maintains the "First-In-First-Out" integrity of levels. - **DFS (Stack - LIFO)**: Whether using the explicit stack or the implicit recursion stack, DFS processes the most recently discovered neighbor first ("Last-In-First-Out"). - **Traversal Order Dependency**: A single graph can yield multiple valid BFS/DFS sequences. These are determined by: - *Starting Vertex*: Shifting the root changes the discovery timestamps. - *Adjacency List Ordering*: The order in which neighbors are stored in the list determines which neighbor is enqueued/pushed first. - **Recursive vs. Iterative DFS**: While recursive DFS is the standard implementation, the Recursion Stack has finite depth. In very deep graphs, recursive DFS will trigger a Stack Overflow. Iterative DFS, using an explicit stack on the heap, avoids this limit but requires careful manual state management. ### 4. Breadth-First Search (BFS): Layered Exploration BFS is the definitive algorithm for Minimum Edge Paths in unweighted graphs. Because it explores level-by-level, the first discovery of a node is guaranteed to be the shortest path from the source. **BFS Pseudocode Template:** ```javascript BFS(G, start_node): Visited[V] = {false} Queue Q Visited[start_node] = true Q.enqueue(start_node) while Q is not empty: u = Q.dequeue() for each neighbor v of u: if Visited[v] is false: Visited[v] = true // MARK IMMEDIATELY Q.enqueue(v) ``` **Complexity and Applications:** - **Time Complexity**: $O(V + E)$ for adjacency lists; $O(V^2)$ for adjacency matrices. - **Bipartite Checking**: A graph is bipartite if there are no "cross-edges" between vertices at the same level. - **Shortest Path**: BFS distance corresponds exactly to the level number in the BFS tree. > **GATE Trap**: Always mark a node as visited before pushing it into the queue. If you wait until it is dequeued to mark it, the same node may be enqueued multiple times from different paths, potentially leading to $O(2^V)$ time complexity and a Memory Limit Exceeded (MLE) error. ### 5. Depth-First Search (DFS): Recursive Descent DFS is the foundation for connectivity analysis, cycle detection, and topological ordering. **DFS Pseudocode (Recursive):** ```javascript DFS(G): Visited[V] = {false} for each v in V: if Visited[v] is false: DFS_Visit(G, v) DFS_Visit(G, u): Visited[u] = true Discovery_Time[u] = ++time for each neighbor v of u: if Visited[v] is false: DFS_Visit(G, v) Finishing_Time[u] = ++time ``` **DFS Edge Classification (Directed vs. Undirected):** One of the most frequent MSQ (Multiple Select Question) areas in GATE: - **Tree Edges**: Edges in the DFS forest. - **Back Edges**: Edges pointing to an ancestor in the DFS tree. Presence of a back edge = Cycle. - **Forward Edges**: (Directed Only) Edges pointing to a non-child descendant. - **Cross Edges**: (Directed Only) Edges between branches or components. - **Critical Note**: In Undirected Graphs, only Tree Edges and Back Edges exist. Forward and Cross edges are impossible because any "cross" edge would have been explored as a Tree or Back edge during the recursive descent. ### 6. Comprehensive Complexity Analysis In GATE, space complexity must account for both the auxiliary data structure and the visited array. | Representation | Time Complexity | Auxiliary Space (Total) | Strategic Note | | :--- | :--- | :--- | :--- | | **BFS (List)** | $O(V + E)$ | $O(V)$ | Queue: $O(W)$, Visited: $O(V)$ | | **BFS (Matrix)** | $O(V^2)$ | $O(V)$ | Inefficient for Sparse Graphs | | **DFS (List)** | $O(V + E)$ | $O(V)$ or $O(V+E)$ | Stack: $O(H)$, Visited: $O(V)$ | | **DFS (Matrix)** | $O(V^2)$ | $O(V)$ | Better for Dense Graphs ($E \approx V^2$) | | **DSU (Connectivity)** | $O(V + E \log V)$ | $O(V)$ | Alternative for counting components | **Memory Behavior:** - **BFS Space**: Controlled by the graph's maximum Width ($W$). - **DFS Space**: Controlled by the graph's maximum Height ($H$). - **Total Auxiliary Space**: Regardless of $W$ or $H$, the visited array always adds a baseline $O(V)$ requirement. ### 7. Strategic Comparison: BFS vs. DFS | Feature | Breadth-First Search (BFS) | Depth-First Search (DFS) | | :--- | :--- | :--- | | **Data Structure** | Queue (FIFO) | Stack (LIFO) | | **Strategy** | Level-by-level | Branch-by-branch | | **Shortest Path** | Guarantees Min-Edge path | No guarantee | | **Cycle Detection** | Via Cross Edges at same level | Via Back Edges | | **Memory Failure** | Memory Limit Exceeded (MLE) | Stack Overflow | | **Primary Use** | Shortest path, Bipartite check | Connectivity, Topo Sort, Cycles | ### 8. Impact of Graph Representation Representation dictates the efficiency of the neighbor-discovery loop. - **Adjacency Matrix**: Scanning neighbors always takes $O(V)$, leading to $O(V^2)$ total time. Use only for dense graphs. - **Adjacency List**: Scanning neighbors takes $O(\text{degree}(u))$, leading to $O(V+E)$. - **GATE Trap (Undirected Lists)**: In an undirected adjacency list, every edge $(u, v)$ appears twice (once at $u$, once at $v$). Always divide the sum of list lengths by 2 to get the edge count $E$. ### 9. Traversal-Based Problem Identification Heuristics - `"Shortest path" / "Minimum edges" / "Fewest hops"` $\rightarrow$ BFS. - `"Dependencies" / "Pre-requisites" / "Task ordering"` $\rightarrow$ Topological Sort. - `"Connected Components"` $\rightarrow$ DFS (simple to implement) or DSU (efficient for dynamic edges). - `"Critical point" / "Single point of failure"` $\rightarrow$ Articulation Points. - `"Cycles in directed graph"` $\rightarrow$ DFS (Look for Back Edges). ### 10. Classic Traversal Problems (GATE Focus) - **Connected Components**: Initiate a traversal. If any nodes remain unvisited, restart from an unvisited node. The number of restarts equals the number of components. Complexity: $O(V+E)$. - **Cycle Detection**: - *DFS Rule*: If you encounter a Back Edge (a neighbor currently in the recursion stack), a cycle exists. - *BFS Rule*: If you encounter a Cross Edge between vertices at the same level, a cycle exists. - **Articulation Points (Critical Nodes)**: A vertex $u$ is an articulation point if its removal disconnects the graph. - *Root of DFS Tree*: Articulation point if it has $>1$ child node. - *Non-root vertex $u$*: Articulation point if it has a child $v$ such that no vertex in the subtree rooted at $v$ has a back-edge to $u$ or any ancestor of $u$. (i.e., the "low-link" value of $v \geq$ discovery time of $u$). - **Bipartite Graph (2-Colorability)**: - *BFS Method*: Check for cross-edges at the same level. If none exist, it is bipartite. - *DFS Method*: A graph is bipartite if there are no back edges between vertices that are both at odd levels or both at even levels. - **Topological Sort (DAGs Only)**: Linear ordering where for edge $u \to v$, $u$ appears before $v$. - *DFS Approach*: The topological sort is the reverse of the DFS finishing times (popping order). - *Kahn's Algorithm*: Indegree-based. Repeatedly remove vertices with Indegree 0, add them to the sort, and decrement the indegree of their neighbors. ### 11. Advanced Traversal Nuances - **Multi-source BFS**: Start with multiple nodes in the queue (distance 0). Useful for finding the distance to the nearest "target" (e.g., nearest gas station) for all nodes simultaneously. - **0-1 BFS**: When edge weights are only 0 or 1, use a Deque. If the edge weight is 0, `push_front`; if 1, `push_back`. This is a simplified version of Dijkstra's algorithm. - **DFS Timestamps for DAGs**: In any DAG, for every directed edge $(u, v)$, the finishing time $f[v]$ must be less than $f[u]$. Encountering $f[v] > $f[u]$ while $v$ is still in the stack implies a back-edge and thus a cycle. ### 12. Common GATE PYQ Patterns & Strategy - **Stack/Queue State Prediction**: You will be given a graph and an adjacency list order. You must simulate the traversal and provide the state of the Stack/Queue after $k$ steps. - **Validity of Traversal**: "Which of the following is NOT a valid DFS/BFS order?" Remember: Adjacency list order is arbitrary, but the level-by-level (BFS) or depth-wise (DFS) logic must be strictly maintained. - **Edge Classification**: Given discovery/finishing times, classify a specific edge. - $d[u] < d[v] < f[v] < f[u] \implies$ Tree/Forward Edge. - $d[v] < d[u] < f[u] < f[v] \implies$ Back Edge. - $f[v] < d[u] \implies$ Cross Edge. ### 13. Fast Revision "Cheat Sheet" | Rule | Condition / Property | | :--- | :--- | | **Acyclicity** | No Back Edges (DFS) or No Cross Edges at same level (BFS) | | **Shortest Path** | BFS (Unweighted only) or Dijkstra ($O(E \log V)$ for weighted) | | **Topological Sort** | DAGs only; reverse of DFS popping order | | **Bipartite** | No back edges between same-parity levels (DFS) | | **Articulation Point** | Root with children $>1$ OR child with no back-edge above $u$ | **Most Repeated Topics:** - Topological Sort: Always verify the graph is a DAG. - Edge Classification: Know the directed vs. undirected differences. - Complexity: Distinguish between Matrix ($V^2$) and List ($V+E$). **Common Mistakes to Avoid:** - **The Mark Trap**: Forgetting to mark BFS nodes visited during enqueuing. - **Cycle Blindness**: Assuming a graph is a DAG without confirming the absence of back edges. - **Directional Error**: Applying undirected graph properties (like "only tree/back edges") to directed graph problems. - **Stack Confusion**: Forgetting that DFS finishing time is the order in which nodes are popped, not pushed.

Q121MediumMSQ

Which of the following graph properties can be determined using BFS in $O(V + E)$ time?

🚀 Solve in Practice Mode

📖 Explanation

(A) TRUE: Run BFS from any vertex - if all $V$ vertices are visited, the graph is connected. $O(V+E)$ . (B) TRUE: 2-colour the graph during BFS - if a conflict is found, it is not bipartite. $O(V+E)$ . (C) FALSE: Finding all-pairs shortest paths requires running BFS $V$ times - $O(V(V+E))$ total, not $O(V+E)$ . (D) TRUE: During BFS, if we encounter a visited vertex that is not the parent of the current vertex (in undirected graphs), a cycle exists. $O(V+E)$ .

Q122MediumMCQ

DFS traversal order depends on:

🚀 Solve in Practice Mode

Q123MediumMCQ

Consider an unweighted undirected graph G with 6 vertices {1, 2, 3, 4, 5, 6} and edges: (1,2), (1,3), (2,4), (2,5), (3,5), (3,6). A Breadth-First Search (BFS) is performed starting from vertex 1. If, during the BFS, neighbors are enqueued in increasing order of their vertex labels, which of the following sequences represents a valid BFS traversal?

🚀 Solve in Practice Mode

Q124MediumMCQ

Breadth First Search (BFS) on a graph with $V$ vertices and $E$ edges uses which data structure to track the order of vertex exploration?

🚀 Solve in Practice Mode

📖 Explanation

BFS uses a queue (FIFO - First In First Out) to track which vertex to visit next. When a vertex $u$ is visited, all its unvisited neighbours are added to the back of the queue, and the next vertex to explore is dequeued from the front. This ensures vertices are visited in order of increasing distance from the source, producing a level-by-level traversal.

Q125MediumMSQ

Which of the following statements about topological sorting are TRUE?

🚀 Solve in Practice Mode

Q126MediumMCQ

Topological sorting of a Directed Acyclic Graph (DAG) using DFS is based on which of the following principles?

🚀 Solve in Practice Mode

Q127MediumMSQ

Which of the following statements about the rank in Union-Find with union by rank are TRUE?

🚀 Solve in Practice Mode

Q128MediumMSQ

Which of the following problems can be solved efficiently using Union-Find?

🚀 Solve in Practice Mode

Q129MediumNAT

Consider BFS on the following graph starting from vertex $A$ . Vertices: $\{A, B, C, D, E\}$ . Edges: $(A,B), (A,C), (B,D), (C,D), (D,E)$ . What is the shortest path distance from $A$ to $E$ ?

🚀 Solve in Practice Mode

📖 Explanation

BFS from $A$ : Level 0: $\{A\}$ , $d[A]=0$ . Level 1: $\{B, C\}$ , $d[B]=1$ , $d[C]=1$ . Level 2: $\{D\}$ (reached via $B$ or $C$ ), $d[D]=2$ . Level 3: $\{E\}$ , $d[E]=3$ . The shortest path from $A$ to $E$ is $A \to B \to D \to E$ (or $A \to C \to D \to E$ ), both of length $\mathbf{3}$ .

Q130MediumMCQ

Consider a sequence of n-1 UNION operations and m FIND operations on n elements using Union-Find with union by rank and path compression. Which of the following correctly summarizes the total time complexity?

🚀 Solve in Practice Mode

Q131MediumNAT

Consider a graph $G$ with $V$ vertices and $E$ edges. The number of connected components found by running BFS from every unvisited vertex is $k$ . How many total edges does the BFS forest (union of all BFS trees) contain?

🚀 Solve in Practice Mode

📖 Explanation

Each BFS tree rooted at a source in its connected component is a spanning tree of that component. If component $i$ has $V_i$ vertices, its BFS tree has $V_i - 1$ edges. Total edges in the BFS forest $= \sum_{i=1}^{k} (V_i - 1) = \sum V_i - k = V - k$ . For a connected graph ( $k=1$ ), the BFS tree has $V-1$ edges (spanning tree). For $k$ components, the forest has $V - k$ edges.

Q132MediumMCQ

Consider a directed graph G = (V, E). Depth First Search (DFS) is performed on G starting from vertex s. Which of the following statements about DFS traversal is correct?

🚀 Solve in Practice Mode

Q133MediumMCQ

BFS starting from vertex $s$ in an unweighted graph computes the shortest path distance from $s$ to all reachable vertices. Why does BFS guarantee shortest paths in unweighted graphs?

🚀 Solve in Practice Mode

📖 Explanation

BFS processes vertices in order of their distance from the source $s$ . All vertices at distance 1 are enqueued first, then distance 2, and so on. When a vertex $v$ is first dequeued and its distance $d[v]$ is set, no shorter path can exist - because all vertices at distance $< d[v]$ have already been processed. This level-by-level property guarantees that the first time BFS reaches a vertex, it is via the shortest (minimum hop) path.

Q134MediumMCQ

An unweighted, undirected graph G has N vertices and M edges. A BFS algorithm is typically implemented using an adjacency list representation. If the graph is represented by an adjacency matrix instead, how would the worst-case time complexity of BFS change, assuming N is large?

🚀 Solve in Practice Mode

Q135MediumMCQ

Consider performing the following sequence on a Union-Find structure with 6 elements {1,...,6} using union by rank with path compression. Operations: UNION(1,2), UNION(3,4), UNION(5,6), UNION(1,3), UNION(1,5), FIND(6). After FIND(6) with path compression, what is parent[6]?

🚀 Solve in Practice Mode

Q136MediumNAT

The time complexity of topological sorting using DFS on a graph with V vertices and E edges is:

🚀 Solve in Practice Mode

Q137MediumMCQ

The inverse Ackermann function α(n) used in the complexity analysis of Union-Find is practically considered constant. Which of the following best describes α(n)?

🚀 Solve in Practice Mode

Q138MediumMSQ

The BFS tree of a graph rooted at source $s$ has the property that for every vertex $v$ in the tree, $d[v]$ represents the shortest path distance from $s$ to $v$ in the original graph. Which of the following are TRUE about the BFS tree?

🚀 Solve in Practice Mode

📖 Explanation

(A) TRUE: In undirected BFS, all non-tree edges connect vertices at the same level or adjacent levels - these are cross edges. Back edges (to ancestors) don't occur in BFS of undirected graphs since both directions are checked. (B) TRUE: For any non-tree edge $(u,v)$ in undirected BFS, $u$ and $v$ are in the same or adjacent BFS levels, so $|d[u] - d[v]| \leq 1$ . (C) FALSE: BFS tree is a spanning tree only if the graph is connected. For disconnected graphs, BFS from one source doesn't reach all vertices. (D) FALSE: The depth of the BFS tree from source $s$ gives the maximum distance from $s$ (eccentricity of $s$ ), not the diameter (which requires BFS from all vertices or specific algorithms).

Q139MediumMCQ

In the iterative implementation of DFS using an explicit stack, which of the following issues may arise compared to the recursive implementation?

🚀 Solve in Practice Mode

Q140MediumMCQ

In Kosaraju's algorithm for finding Strongly Connected Components (SCCs), DFS is performed twice. Which of the following correctly describes the two phases?

🚀 Solve in Practice Mode