Graph Traversal – GATE CSE AlgorithmsPractice Questions & PYQs

In a depth-first search (DFS) tree $T$, every edge incident to a leaf $u$ in the graph $G$ must either be a tree edge (connected to its parent $p(u)$) or a back-edge (connected to an ancestor $w$). Since $deg_G(u) \ge 2$, there must exist at least one back-edge $(u, w)$ in $G$. This back-edge $(u, w)$ creates a cycle in $G$ composed of the edge $(u, w)$ and the unique path in $T$ from $w$ to $u$. This cycle necessarily contains $u$ and its neighbors involved in the cycle path, which, by the properties of DFS trees, effectively incorporates $u$ and its connections. Among the choices, this structure identifies the required cyclic relationship involving $u$ and its neighbors.

In a depth-first traversal of a graph with $n$ vertices, the DFS forest partitions the graph into $c$ connected components. Each connected component containing $v_i$ vertices forms a spanning tree with $v_i - 1$ edges. The total number of tree edges $k$ is the sum of edges across all components:
$k = \sum_{i=1}^{c} (v_i - 1) = \left(\sum_{i=1}^{c} v_i\right) - \sum_{i=1}^{c} 1$.
Since the total number of vertices $n = \sum_{i=1}^{c} v_i$ and the sum of $1$ for $c$ components is simply $c$, we have $k = n - c$.
Solving for the number of connected components, we obtain $c = n - k$.

A Depth First Search (DFS) traversal visits nodes by exploring as far as possible along each branch before backtracking. We verify the existence of edges for each sequence:

1. (I) $a, b, e, g, h, f$: Edges $(a,b), (b,e), (e,g), (g,h), (h,f)$ all exist in the graph. This is a valid DFS.
2. (II) $a, b, f, e, h, g$: This sequence suggests a path from $f$ to $e$. No edge $(f,e)$ exists in the graph, so this is invalid.
3. (III) $a, b, f, h, g, e$: Edges $(a,b), (b,f), (f,h), (h,g), (g,e)$ exist. This is a valid DFS.
4. (IV) $a, f, g, h, b, e$: Edges $(a,f), (f,g), (g,h), (h,b), (b,e)$ exist. This is a valid DFS.

Since (I), (III), and (IV) represent valid DFS traversals, option D is the correct choice.

In a breadth-first traversal (BFS), nodes are discovered in non-decreasing order of their shortest distance from the source $r$. BFS systematically explores all nodes at a distance $k$ before any node at distance $k+1$. Let $d(r, u)$ and $d(r, v)$ denote the shortest path lengths from $r$ to $u$ and $v$, respectively. If node $u$ is visited before node $v$, it implies that $u$ is either in the same "layer" as $v$ or in a layer closer to the source than $v$. Consequently, the shortest path distance to $u$ must be less than or equal to the shortest path distance to $v$, satisfying $d(r, u) \le d(r, v)$.

In a DFS traversal, if vertex $u$ has an unvisited neighbor, the algorithm moves to that neighbor $v$, creating an edge $(u, v)$ in the DFS tree $T$. If the first new vertex $v$ visited after $u$ is not a neighbor of $u$ (i.e., $(u, v) \notin E(G)$), it implies that $u$ had no unvisited neighbors during its exploration. Since $u$ has no unvisited neighbors, the algorithm must backtrack from $u$. This indicates that all subtrees rooted at the children of $u$ have already been fully explored. Consequently, $u$ cannot have any children in $T$, meaning $u$ must be a leaf node.

Recursive DFS uses the call stack implicitly to keep track of vertices.

DFS visits each vertex once and explores each edge once, resulting in O(V + E).

DFS explores as deep as possible along each branch before backtracking. It does not guarantee shortest path or level-wise traversal.

A topological sort requires at least one node to have no incoming edges to initiate the ordering process. This starting node can be considered the 'source' of the topological order.

In worst case (linear chain), recursion depth equals number of vertices.

Topological sorting relies on the absence of cycles. It produces a linear ordering of nodes where for every directed edge (u, v), node u comes before node v in the ordering. A DAG can have multiple valid topological orderings, reflecting different ways to arrange the nodes while satisfying the dependency constraints.

In a DAG, each edge contributes to a single node having an outgoing edge. With 5 edges, a maximum of 5 nodes can have outgoing edges. This implies that at most one node can have no outgoing edges.

Kahn's algorithm is based on identifying nodes with no incoming edges and removing them iteratively. It uses a queue to efficiently manage these nodes. It cannot be applied to graphs with cycles, as cycles imply the existence of dependencies that cannot be linearly ordered.

Kosaraju's algorithm uses DFS twice to find strongly connected components.

Discovery and finishing times help identify back edges and ordering for topological sort.

DFS tree of a connected graph is a spanning tree with V-1 edges.

A DFS-based topological sort involves performing a Depth First Search and reversing the order of nodes in the traversal output. This ensures that nodes that are visited later in the DFS, and thus depend on earlier nodes, appear earlier in the topological order.

With adjacency matrix, we scan all vertices for each node, leading to O(V^2).

BFS visits vertices level by level - first the root (level 0), then all children of the root (level 1), then all grandchildren (level 2), and so on. This is exactly the level-order traversal of a tree. It is also sometimes called breadth-first traversal of a tree. Preorder visits root then subtrees (DFS-like); inorder and postorder are also DFS-based traversals specific to binary trees.

DFS is used for topological sorting (by ordering vertices in decreasing finish time) and for finding strongly connected components (Kosaraju's and Tarjan's algorithms). Shortest path in unweighted graphs uses BFS. Minimum spanning trees use Prim's or Kruskal's algorithms.