Computer Sciences > GATE 2026 SET-1 > Graph Algorithms
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V, E) as input, where d[v] and f[v] are the discovery time and finishing time, respectively, of the vertex v ∈ V.
DFS(G): unmark all v ∈ V; t ← 0; for each v ∈ V: if v is unmarked: t ← Explore(G, v, t)
Explore(G, v, t): mark v; t ← t+1; d[v] ← t; for each (v,w) ∈ E: if w is unmarked: t ← Explore(G, w, t); t ← t+1; f[v] ← t; return t
Suppose that the input directed graph G(V, E) is a directed acyclic graph (DAG).
For an edge (u, v) ∈ E, which of the following options will NEVER be correct?
DFS(G): unmark all v ∈ V; t ← 0; for each v ∈ V: if v is unmarked: t ← Explore(G, v, t)
Explore(G, v, t): mark v; t ← t+1; d[v] ← t; for each (v,w) ∈ E: if w is unmarked: t ← Explore(G, w, t); t ← t+1; f[v] ← t; return t
Suppose that the input directed graph G(V, E) is a directed acyclic graph (DAG).
For an edge (u, v) ∈ E, which of the following options will NEVER be correct?
Correct : b,d
Similar Questions
Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let...
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the foll...
Consider the following algorithm someAlgo that takes an undirected graph G as input.
The output of someAlgo (T) for the tree shown in the given figure is _____...
Total Unique Visitors
Loading......