Graph Traversal – GATE CSE AlgorithmsPractice Questions & PYQs

(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)$.

DFS order depends on how neighbors are arranged in adjacency list.

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

1. Initialize: Q = [1], V = {}
2. Dequeue 1. V = {1}. Neighbors of 1 are 2, 3. Enqueue them in increasing order. Q = [2, 3]. Traversal order: [1]
3. Dequeue 2. V = {1, 2}. Neighbors of 2 are 1, 4, 5. (1 is visited). Enqueue 4, 5 in increasing order. Q = [3, 4, 5]. Traversal order: [1, 2]
4. Dequeue 3. V = {1, 2, 3}. Neighbors of 3 are 1, 5, 6. (1 is visited, 5 is already in Q). Enqueue 6. Q = [4, 5, 6]. Traversal order: [1, 2, 3]
5. Dequeue 4. V = {1, 2, 3, 4}. Neighbors of 4 are 2, 6. (2 is visited, 6 is already in Q). No new nodes to enqueue. Q = [5, 6]. Traversal order: [1, 2, 3, 4]
6. Dequeue 5. V = {1, 2, 3, 4, 5}. Neighbors of 5 are 2, 3. (Both are visited). No new nodes to enqueue. Q = [6]. Traversal order: [1, 2, 3, 4, 5]
7. Dequeue 6. V = {1, 2, 3, 4, 5, 6}. Neighbors of 6 are 3, 4. (Both are visited). No new nodes to enqueue. Q = []. Traversal order: [1, 2, 3, 4, 5, 6]
   The final BFS traversal sequence is 1, 2, 3, 4, 5, 6.

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.

A: TRUE - if at any step more than one vertex has in-degree 0, multiple valid orderings exist by choosing different vertices first. B: TRUE - both DFS-based and Kahn's algorithm run in O(V + E). C: FALSE - only DAGs have topological orderings; graphs with cycles do not. D: TRUE - the first vertex in a topological order has no predecessor in the ordering, meaning no edge enters it from an earlier vertex, so its in-degree in the original graph must be 0.

In DFS-based topological sorting, after DFS completes on a vertex (i.e., it is fully explored and its finish time is recorded), it is added to the front of a list. The final list in reverse finish-time order gives the topological order. This works because in a DAG, if there is an edge (u, v), then f[v] < f[u].

A: TRUE - rank is defined as an upper bound on tree height; union by rank maintains this invariant. B: TRUE - rank only increases (when two equal-rank roots merge) and never decreases during any operation. C: TRUE - path compression flattens the tree, potentially making the actual height less than the rank (since rank is now only an upper bound, not the actual height). D: TRUE - rank increments only when UNION merges two trees with equal rank, making the combined tree's rank one higher. If ranks differ, the lower-rank tree attaches to the higher-rank root with no rank change.

A: TRUE - Union-Find handles online edge insertions and connectivity queries efficiently: UNION for insertions, FIND for connectivity checks, O(α(n)) per operation. C: TRUE - initialize n components; after all UNION operations, count distinct roots using FIND on each element; components = distinct roots. D: TRUE - for each new edge (u,v), if FIND(u)==FIND(v) a cycle is detected; otherwise UNION(u,v). B: FALSE - Union-Find does NOT support edge deletions. Handling deletions requires more complex data structures like link-cut trees or offline algorithms (e.g., offline dynamic connectivity using divide and conquer on time).

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}$.

With union by rank and path compression: each MAKE-SET is O(1) (total O(n) for n elements). Each UNION is O(α(n)) amortized. Each FIND is O(α(n)) amortized. For n-1 UNIONs and m FINDs: total = O(n) + O((n-1) α(n)) + O(m α(n)) = O((n+m) α(n)). Since α(n) ≤ 4 for all practical n, this is essentially O(n+m) in practice. This is the tight bound proven by Tarjan.

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.

DFS can detect cycles in a directed graph by checking for back edges. During DFS, if a back edge (u, v) is found where v is an ancestor of u in the DFS tree, a cycle exists. DFS uses a stack (or recursion), not a queue. Its time complexity is O(V + E). The traversal order depends on adjacency list ordering.

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.

1. Adjacency List Representation:

   • Each vertex is enqueued and dequeued at most once. For each vertex 'u' dequeued, its neighbors are iterated through its adjacency list. The sum of lengths of all adjacency lists in an undirected graph is 2M (since each edge (u,v) appears in u's list and v's list).
   • Therefore, the total time complexity is O(N + M).

2. Adjacency Matrix Representation:

   • Each vertex is enqueued and dequeued at most once. When a vertex 'u' is dequeued, to find its neighbors, the algorithm must scan the entire row 'u' in the adjacency matrix. This scan takes O(N) time (to check connectivity to N other vertices).
   • Since each of the N vertices is processed (dequeued and its row scanned) exactly once, the total time complexity becomes O(N * N) = O(N^2).

Thus, the time complexity changes from O(N+M) to O(N^2).

Trace with union by rank: Initial ranks all 0. UNION(1,2): tie→rank[1]=1, parent[2]=1. UNION(3,4): tie→rank[3]=1, parent[4]=3. UNION(5,6): tie→rank[5]=1, parent[6]=5. UNION(1,3): rank[1]=rank[3]=1, tie→rank[1]=2, parent[3]=1. UNION(1,5): rank[1]=2 > rank[5]=1 → parent[5]=1. Tree: 1 is root; children of 1: {2,3,5}; children of 3: {4}; children of 5: {6}. FIND(6): traverse 6→5→1 (root found). Path compression: parent[6]=1, parent[5]=1 (already). After FIND(6): parent[6] = 1.

DFS-based topological sort runs a complete DFS on the graph, which visits every vertex once and traverses every edge once. This takes O(V + E) time - O(V) for vertex initialization and O(E) for edge traversal. Inserting each vertex onto the stack (or output list) upon finishing takes O(1) per vertex. Kahn's algorithm also runs in O(V + E): computing all in-degrees is O(V + E), queue operations are O(V), and processing each edge to decrement in-degrees is O(E).

The inverse Ackermann function α(n) is defined as the inverse of the Ackermann function A(k,k). The Ackermann function grows extraordinarily fast - A(4,4) is a number with more digits than atoms in the observable universe. Therefore α(n) ≤ 4 for all n smaller than A(4,4), which includes every conceivable input in computing. Technically α(n) → ∞ as n → ∞ (so it is NOT O(1) in the strict mathematical sense), but for all practical purposes it is treated as a constant ≤ 4.

(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).

When implementing DFS iteratively, if all neighbors are pushed onto the stack at once, they are processed in reverse order compared to recursive DFS (due to LIFO behavior). To match recursive DFS exactly, neighbors must be pushed in reverse order. Both approaches produce valid DFS traversals but potentially different orderings.

Kosaraju's algorithm: (1) Perform DFS on the original graph and record finish times. (2) Compute the transpose of the graph. (3) Perform DFS on the transposed graph, processing vertices in decreasing order of finish time from step 1. Each DFS tree in step 3 corresponds to one SCC.