Graph Traversal – GATE CSE AlgorithmsPractice Questions & PYQs

A back edge (u, v) means v is an ancestor of u in the DFS tree. Since v was discovered before u and u finishes before v, we have d[v] < d[u] < f[u] < f[v]. This is the hallmark of back edges and indicates the presence of a cycle.

(A) TRUE: BFS guarantees shortest (minimum hop) paths in unweighted graphs. (B) TRUE: During BFS, if a visited vertex is encountered that is not the parent of the current vertex, a cycle exists. (C) TRUE: Run BFS from each unvisited vertex; each BFS call discovers one connected component. (D) FALSE: Topological sorting requires DFS (using finish times) or Kahn's algorithm (which uses in-degree reduction with a queue, but this is not standard BFS). Standard BFS does not produce a topological order.

Kosaraju's algorithm uses two DFS passes (original and transposed graph). Tarjan's algorithm uses one DFS with low-link values for SCCs. Bridge finding in undirected graphs uses DFS with low values (similar to articulation point detection). Prim's algorithm uses a priority queue / greedy approach and does not use DFS.

Finding all connected components using Union-Find: Step 1 - n MAKE-SET operations: O(n). Step 2 - for each of m edges (u,v): perform FIND(u) and FIND(v) - O(α(n)) each; if different components, perform UNION(u,v) - O(α(n)). Total for m edges: O(m α(n)). Overall complexity: O(n + m α(n)) = O((n+m) α(n)). Since α(n) is practically constant, this is essentially O(n + m) - linear in the size of the graph.

For an adjacency matrix representation, BFS must scan an entire row of $V$ entries to find all neighbours of a vertex. Since there are $V$ vertices, the total time to find all neighbours is $O(V^2)$. Even if the graph is sparse (few edges), the adjacency matrix representation forces BFS to check all $V$ entries per vertex. For adjacency list, BFS is $O(V+E)$ - the preferred representation for sparse graphs.

The grid graph has $V = mn$ vertices and $E = O(mn)$ edges (each cell has at most 4 neighbours). BFS time complexity $= O(V + E) = O(mn + mn) = O(mn)$. Each cell is visited at most once, and for each cell at most 4 neighbours are checked. Total operations $= O(mn)$. This is a classic BFS application - finding shortest path in a maze or grid.

Topological order by decreasing finish time: f[1]=14 (first), f[4]=13 (second), f[7]=12 (third), f[2]=11 (fourth), ... Vertices before vertex 2 are: vertex 1 (f=14), vertex 4 (f=13), vertex 7 (f=12). That gives 3 vertices before vertex 2. Wait - position of 2 is 4th, so 3 vertices appear before it. Answer is 3.

For a valid topological ordering, every edge (u→v) must have u before v. Check option A: A→C(A before C ✓), A→D(✓), B→D(B before D ✓), B→E(✓), C→F(C before F ✓), D→F(✓), D→G(✓), E→G(✓). All edges satisfied - A is valid. Check option B: A→C requires A before C, but A appears after B,E,D - need to verify C appears after A: B,A,E,D,C... A is 2nd, C is 5th ✓. But B→D: B is 1st, D is 4th ✓. D→F: D is 4th, F is 7th ✓. Actually B might also be valid. Option A is clearly valid and the most straightforward.

BFS from vertex $1$: Queue: $[1]$. Dequeue $1$, enqueue neighbours $2, 3$ → Queue: $[2, 3]$. Dequeue $2$, enqueue neighbours $4, 5$ → Queue: $[3, 4, 5]$. Dequeue $3$, enqueue neighbour $6$ → Queue: $[4, 5, 6]$. Dequeue $4$ (no unvisited neighbours) → Queue: $[5, 6]$. Dequeue $5$ (no unvisited neighbours) → Queue: $[6]$. Dequeue $6$ → Queue: $[]$. BFS order: $1, 2, 3, 4, 5, 6$.

Let's trace the BFS step-by-step and observe the queue (Q) and visited set (V):

1. Initialization: Q = [1], V = {}
2. Dequeue 1. Mark 1 as visited (V = {1}). Neighbors of 1 are 2, 3. Enqueue 2, then 3. Q = [2, 3].
3. Dequeue 2. Mark 2 as visited (V = {1, 2}). Neighbors of 2 are 1, 4, 5. (1 is visited). Enqueue 4, then 5. Q = [3, 4, 5].
4. Dequeue 3. Mark 3 as visited (V = {1, 2, 3}). Neighbors of 3 are 1, 5, 6. (1 is visited). Vertex 5 is already in the queue, so it's not enqueued again. Enqueue 6. Q = [4, 5, 6].
   At this point, immediately after vertex 3 is dequeued and its neighbors processed, the content of the queue is [4, 5, 6].

Path compression during FIND(d) traverses the path d→c→b→a→r, finds root r, then sets every node's parent directly to r. After FIND(d): parent[d]=r, parent[c]=r, parent[b]=r, parent[a]=r. All nodes on the path now point directly to the root. Future FIND operations on any of d,c,b,a will take O(1) time (just one hop to the root). This is full path compression (also called path collapsing).

Used in Kruskal's algorithm and connectivity problems.

In-degrees: 1=0, 2=0, 3=1, 4=2, 5=1, 6=3. Initial queue (in-degree 0): {1, 2}. Pick 1 (smaller): output 1. Decrement neighbors 3(→0), 4(→1). Enqueue 3. Queue: {2, 3}. Pick 2: output 2. Decrement neighbors 4(→0), 5(→0). Enqueue 4, 5. Queue: {3, 4, 5}. Pick 3: output 3. Decrement 6(→2). Queue: {4, 5}. Pick 4: output 4. Decrement 6(→1). Queue: {5}. Pick 5: output 5. Decrement 6(→0). Enqueue 6. Queue: {6}. Pick 6: output 6. Final order: 1, 2, 3, 4, 5, 6.

BFS uses a three-colour scheme (CLRS): WHITE = undiscovered, GREY = discovered but not fully processed (in the queue), BLACK = fully processed (dequeued and all neighbours examined). A vertex turns GREY when first enqueued, and turns BLACK when it is dequeued and all its adjacent vertices have been examined. Note that option D is partially correct but incomplete - a vertex with no unvisited neighbours also becomes BLACK when dequeued, but the key event is dequeuing and finishing adjacency list processing.

All three descriptions are equivalent and correct. A graph is bipartite iff it has no odd-length cycle. BFS detects this by 2-colouring: assign the source colour $0$; all its neighbours get colour $1$; their unvisited neighbours get colour $0$; and so on (alternating colours by BFS level). If any edge $(u,v)$ has both $u$ and $v$ with the same colour, a same-level or cross-level odd cycle exists and the graph is not bipartite. An odd-length cycle causes two adjacent vertices to receive the same colour.

In DFS coloring, a back edge (u, v) is one where v is an ancestor of u currently on the DFS stack. Ancestors on the stack are GRAY (discovered but not yet finished). So a back edge always goes from a GRAY vertex to another GRAY vertex. This is the key property used for cycle detection.

DFS is used for topological sorting in Directed Acyclic Graphs.

In DFS of a directed graph, all four types of edges can appear: (1) Tree edges - edges in the DFS tree, (2) Back edges - connect a vertex to an ancestor, (3) Forward edges - connect a vertex to a non-child descendant, (4) Cross edges - connect vertices in different DFS trees or same tree but without ancestor-descendant relationship.

B: TRUE - if the topological ordering is unique (only one valid ordering), the DAG must contain a Hamiltonian path visiting all vertices in that order. This doesn't require edges between every consecutive pair - edges can skip vertices (e.g., 1→3 is allowed) as long as the path 1→2→3→4→5→6 exists and at every step only one vertex is available. D: TRUE - unique topological ordering means at every step of Kahn's algorithm only one vertex has in-degree 0, forcing a single choice. A: FALSE - edges can skip vertices. C: FALSE - only the Hamiltonian path structure is required, not all pairs.

A: TRUE - any directed graph's condensation (contracting each SCC to a single supernode) is a DAG, which can be topologically sorted. C: TRUE - the condensation graph has no cycles (each SCC is collapsed to a single node), making it always a DAG. D: TRUE - Kosaraju's first DFS on the original graph produces finish times that correspond to the reverse topological order of the condensation DAG; the second DFS on the transposed graph processes SCCs in topological order. B: FALSE - topological sorting applies to DAGs; within a non-trivial SCC (size > 1) vertices form cycles, so topological sorting doesn't apply within an SCC.