Graph Traversal – GATE CSE AlgorithmsPractice Questions & PYQs

Initial state: parent = [1,2,3,4,5], rank = [0,0,0,0,0]. UNION(1,2): rank[1]=rank[2]=0, tie → 1 becomes root, rank[1]=1. parent[2]=1. UNION(3,4): rank[3]=rank[4]=0, tie → 3 becomes root, rank[3]=1. parent[4]=3. UNION(2,3): FIND(2)=1 (rank 1), FIND(3)=3 (rank 1), tie → 1 becomes root (first argument), rank[1]=2. parent[3]=1. Now FIND(4): parent[4]=3, parent[3]=1 → root is 1. Root of element 4 = 1.

Computing the longest path in a DAG: Step 1 - perform topological sort in O(V + E). Step 2 - initialize dist[s] = 0, dist[v] = -∞ for all other vertices. Step 3 - process each vertex u in topological order; for each edge (u, v), update dist[v] = max(dist[v], dist[u] + w(u,v)). Each vertex is processed once and each edge is relaxed once, giving O(V + E) for step 3. Total time = O(V + E). This also works for shortest paths with negative weights in a DAG - unlike general graphs which need Bellman-Ford.

Path compression works during FIND(x): as the algorithm traverses from x up to the root, it sets the parent of every node along the path directly to the root. This flattens the tree so future FIND operations on any node along the path take O(1) time. Path compression does not change the correctness of FIND (it still returns the same root) but dramatically reduces the tree height over time, leading to nearly O(1) amortized cost per operation.

Running BFS from a single source takes $O(V + E)$ time. To find all-pairs shortest paths using BFS, we run BFS from each of the $V$ vertices as the source. Total time $= V \times O(V + E) = O(V(V + E))$. This is more efficient than using Dijkstra for each vertex in dense unweighted graphs since we leverage the $O(V+E)$ BFS instead of $O((V+E)\log V)$ Dijkstra.

A connected graph with n vertices and n-1 edges is a tree. As a directed tree (DAG), if it is a directed path (each vertex has at most one outgoing and one incoming edge), the topological sort is unique (C). However, a directed tree can also be an arborescence (rooted tree with edges going away from root) where a parent has multiple children - in this case multiple children can be visited in any order, yielding multiple topological sorts (D). Both C and D are possible depending on the structure. If G is specifically a directed path, C holds; if it's a branching tree, D holds.

The Union-Find data structure supports exactly two operations: FIND(x) - returns the representative (canonical element or root) of the set containing x; this allows checking if two elements belong to the same set by comparing their representatives. UNION(x, y) - merges the two disjoint sets containing x and y into one set. These two operations together enable efficient tracking of connected components, cycle detection, and MST construction (Kruskal's algorithm).

In-degree of a vertex is the number of directed edges coming into it. A: no incoming edges → in-degree 0. B: one incoming edge from A → in-degree 1. C: one incoming edge from A → in-degree 1. D: two incoming edges from B and C → in-degree 2. In-degree sequence: A=0, B=1, C=1, D=2. Kahn's starts by enqueuing A (only vertex with in-degree 0), then processes B and C (both reach in-degree 0 after A is processed), then D.

For graphs with edge weights $\in \{0, 1\}$, 0-1 BFS using a deque solves the single-source shortest path problem in $O(V + E)$ time. When relaxing a weight-0 edge $(u,v)$: $v$ is pushed to the front of the deque (same distance level as $u$). When relaxing a weight-1 edge $(u,v)$: $v$ is pushed to the back (next level). This maintains the invariant that vertices are processed in non-decreasing distance order, like Dijkstra but in $O(V+E)$ instead of $O((V+E)\log V)$.

(A) TRUE: Both BFS and DFS visit each vertex once and each edge once (or twice for undirected) - $O(V+E)$ time with adjacency list. (B) TRUE: BFS processes vertices in non-decreasing distance order, guaranteeing shortest paths. DFS may find longer paths first and does not guarantee shortest paths. (C) TRUE: DFS-based topological sort uses finish times (process vertex when DFS finishes it). Kahn's algorithm uses in-degree and a queue but is not standard BFS. (D) TRUE: BFS explicitly uses a queue; DFS uses a stack (iteratively) or the call stack (recursively).

Topological sort by DFS outputs vertices in decreasing order of finish time. Finish times: A=8, C=7, B=6, D=5, E=4, F=3. Decreasing order: A(8), C(7), B(6), D(5), E(4), F(3). Topological order = A, C, B, D, E, F. This is the DFS-based topological sort: vertices that finish last (highest f value) come first in the topological order.

(A) TRUE: BFS computes shortest (minimum hop) paths in both directed and undirected unweighted graphs. (B) FALSE: If the graph is strongly connected, BFS from any vertex reaches all others (since there is a directed path to every vertex). The statement is false. (C) FALSE: BFS trees do not contain forward edges. In BFS, if edge $(u,v)$ exists and $v$ is already visited, it is a cross edge (to a vertex at the same or adjacent level), not a forward edge (which would go to a non-child descendant in a deeper level). (D) TRUE: In directed BFS, non-tree edges connect vertices within the same level or from lower to higher level (cross edges) - they never go backward to a lower level.

A: TRUE - combining path compression with union by rank gives O(α(n)) amortized per operation, proven by Tarjan. C: TRUE - naive Union-Find (no path compression, no union by rank) can degenerate to a chain of length n, giving O(n) FIND. D: TRUE - union by rank alone guarantees tree height ≤ ⌊log₂n⌋, so FIND takes O(log n) worst case even without path compression. B: FALSE - standard Union-Find does NOT support deletion. Once elements are merged, they cannot be split apart. Rollback (undo of unions) is possible with offline techniques, but general deletion is not supported.