Graph Traversal – GATE CSE AlgorithmsPractice Questions & PYQs

A: Kruskal's algorithm uses Union-Find to check if adding an edge creates a cycle (FIND) and to merge components (UNION), running in O(E log E + E α(V)). B: Connected components - initially each vertex is its own component; for each edge (u,v), UNION(u,v). At the end, elements with the same FIND result are in the same connected component. C: Cycle detection in undirected graphs - for each edge (u,v), if FIND(u) == FIND(v) a cycle exists; otherwise UNION(u,v). D: Dijkstra's algorithm uses a priority queue (min-heap), not Union-Find.

DFS uses recursion or stack for traversal.

In a naive array-based Union-Find without path compression or union by rank, repeated UNION operations can create a degenerate tree (a chain/linked list). For example, unioning elements 1,2,3,...,n in order produces a chain: 1→2→3→...→n. A FIND on element 1 must traverse the entire chain to reach the root, taking O(n) time in the worst case. This motivates the need for optimizations like path compression and union by rank.

(A) TRUE: In undirected BFS, any non-tree edge $(u,v)$ connects $u$ and $v$ which are at BFS levels $d[u]$ and $d[v]$ differing by at most 1 (same or adjacent levels). (B) TRUE: Follows directly from (A) - non-tree edges in undirected BFS are cross edges within the same or adjacent levels. (C) FALSE: In undirected BFS, there are no back edges in the DFS sense. When a visited vertex is encountered, it is because of an undirected cross edge - the 'back edge' concept applies to DFS, not BFS. (D) TRUE: The BFS spanning tree has $V-1$ edges. Total edges $= E$. Non-tree edges $= E - (V-1) = E - V + 1$.

A directed graph has no cycle (DAG) iff DFS produces no back edges - TRUE. Cross edges do appear in directed DFS - TRUE. A directed graph is strongly connected iff DFS from any vertex visits all vertices and DFS on its transpose also visits all vertices from that vertex - TRUE. DFS on adjacency matrix is O(V^2), not O(V+E) - FALSE.

In a complete graph $K_n$, every vertex is directly connected to every other vertex. When BFS starts from $s$, all other $n-1$ vertices are neighbours of $s$ and are placed at BFS level 1 (distance 1 from $s$). There are no vertices at distance 2 or more. Hence the BFS tree has depth $\mathbf{1}$ (root at level 0, all others at level 1), and the BFS tree is a star with $s$ as the center.

Computing a valid task schedule via topological sort takes O(V + E) = O(n + m) time using either Kahn's algorithm or DFS-based topological sort. Kahn's: compute in-degrees O(n + m), process each vertex once O(n), process each edge once O(m). DFS-based: standard DFS is O(n + m). For n tasks and m dependency edges, total time = O(n + m). This is optimal since we must read all n vertices and m edges at minimum.

In Kahn's algorithm, every vertex with in-degree 0 is enqueued and processed. In a DAG, all V vertices will eventually be processed and added to the topological order. If a cycle exists, the vertices in the cycle will never have their in-degree reduced to 0 (since each vertex in a cycle has at least one incoming edge from another cycle vertex). The algorithm terminates with fewer than V vertices in the output. If output size < V, a cycle exists.

Union by size: sizes start at 1 each. UNION(1,2): size[1]=2, parent[2]=1. UNION(3,4): size[3]=2, parent[4]=3. UNION(5,6): size[5]=2, parent[6]=5. UNION(7,8): size[7]=2, parent[8]=7. UNION(1,3): size[1]=size[3]=2, tie → parent[3]=1, size[1]=4. UNION(5,7): size[5]=size[7]=2, tie → parent[7]=5, size[5]=4. UNION(1,5): size[1]=size[5]=4, tie → parent[5]=1, size[1]=8. Final tree rooted at 1: depth of 2=1, depth of 3=1, depth of 4=2, depth of 5=1, depth of 6=2, depth of 7=2, depth of 8=3. Maximum depth = 3.

In a connected undirected graph with n vertices and E edges, DFS produces a spanning tree with exactly n-1 tree edges. Every remaining edge is a back edge. So the number of back edges = E - (n - 1). This is also equal to the cyclomatic complexity or the number of independent cycles.

DFS from 1 visits: 1→2→4→6 (backtrack), then 3→5 (already 6 visited). The DFS tree edges are: (1,2), (2,4), (4,6), (1,3), (3,5). Total = 5 tree edges. Since the graph has 6 vertices, the DFS spanning tree has exactly 6-1 = 5 edges.

Union by size guarantees that the tree height is at most O(log n). Proof: when a tree of size s₁ is attached under a tree of size s₂ ≥ s₁, the resulting tree has size s₁ + s₂ ≥ 2s₁. Any node's depth can increase by at most 1 in each UNION, and its size at least doubles each time its tree is attached under another. A node can be attached at most log₂n times before the total size reaches n. Therefore maximum depth = O(log n), and FIND takes O(log n) worst case.

With both path compression and union by rank, the amortized cost per operation is O(α(n)), where α is the inverse Ackermann function. α(n) grows extremely slowly - for all practical values of n (even n = 2^(2^(2^(2^...)))), α(n) ≤ 4. For a sequence of m operations, total time is O(m × α(n)), which is essentially O(m) in practice. This was proven by Tarjan (1975) and is nearly optimal - no implementation can achieve O(m) in the worst case.

Kahn's algorithm (BFS-based topological sort) maintains a queue of all vertices with current in-degree 0. It repeatedly dequeues a vertex u, adds it to the topological order, and decrements the in-degree of all neighbors v of u. If any neighbor's in-degree drops to 0, it is enqueued. If all V vertices are processed, the result is a valid topological order. If fewer than V vertices are processed, the graph contains a cycle. A stack is used in the DFS-based approach.

In the worst case, the queue can contain up to $O(V)$ vertices simultaneously. Consider a star graph with one central vertex connected to all other $V-1$ vertices. When BFS processes the center, it enqueues all $V-1$ neighbours at once. Hence the maximum queue size is $O(V)$. The space complexity of BFS is therefore $O(V)$ for the queue (plus $O(V)$ for the visited array), giving total space $O(V)$.

DFS visits each vertex exactly once (O(n)) and examines each edge exactly twice in an undirected graph - once from each endpoint (O(m)). Therefore, the total time complexity using an adjacency list is O(n + m) = O(V + E). With an adjacency matrix, the complexity would be O(n^2).

If DFS from source s visits all n vertices, it means every vertex is reachable from s. This does NOT mean the graph is strongly connected (which requires all vertices to be mutually reachable). It also does not imply acyclicity - a DFS can still encounter back edges indicating cycles.

Each vertex is disconnected, so DFS must be called separately for each vertex.

The graph contains a cycle: A→B→C→A. In Kahn's algorithm, vertices in a cycle never have their in-degree reduced to 0 and are never enqueued. In-degrees: A=1(from C), B=2(from A,D), C=1(from B), D=0, E=1(from D), F=1(from E). Initial queue: {D}. Process D: decrement B(→1), E(→0). Enqueue E. Process E: decrement F(→0). Enqueue F. Process F: no outgoing edges. Queue empty. Output: {D, E, F} - only 3 vertices. Vertices A, B, C are stuck in the cycle. Output size = 3 < 6, confirming a cycle exists.

A: Shortest/longest paths in a DAG are computed by processing vertices in topological order and relaxing edges - handles negative weights in O(V+E). B: Critical Path Method processes tasks in topological order to compute earliest/latest start times. C: Kosaraju's algorithm performs DFS on the original graph to get finish times (equivalent to topological order on the condensation graph), then DFS on the transpose in reverse finish order. D: Deadlock detection in OS resource allocation graphs uses cycle detection - the absence of topological order indicates a deadlock cycle.