Register

Memory Based GATE DA 2024 | Question: 27

• recategorized by
954 views
1 1 vote
Consider performing Depth-First Search (DFS) on an undirected and unweighted graph $\bar{G}$ starting at vertex $S$. For any vertex $u$ in $G$, where $d[u]$ is the length of the shortest path from $S$ to $u$, let $(u \geqslant v)$ be an edge in $G$ such that $d[u] < d[v]$.
If $u$ is explored first in the DFS traversal in the direction from $u$ to $v$, then in the above DFS, the edge $(u, v)$ becomes:

  1. A forward edge
  2. A back edge
  3. A cross edge
  4. A tree edge

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · Memory Based GATE DA...Next → · Memory Based GATE DA...
← Previous in category · Memory Based GATE DA...Next in category → · Memory Based GATE DA...
Position:
Show:

Related questions

2 2 votes
1 1 answer
727
727 views
GO Classes asked Feb 4, 2024
727 views
Memory Based GATE DA 2024 | Question: 34
BFS DFS question asking the number of nodes expanded BFS = DFSBFS $$ DFSNone
3 3 votes
1 1 answer
1.2k
1.2k views
GO Classes asked Feb 4, 2024
1,236 views
Memory Based GATE DA 2024 | Question: 18
Consider a directed acyclic graph (DAG) with vertices labeled as P, Q, R, S, T, U, and V. Which of the following sequences represents a possible topological sort of the g...
1 1 vote
1 1 answer
431
431 views
GO Classes asked Feb 12
431 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 38
Suppose the input directed graph $G(V,E)$ is a DAG. For an edge $(u,v)\in E$, which of the following will NEVER be correct in DFS discovery/finish times?$d[u] < d[v] < f[...
0 0 votes
1 1 answer
540
540 views
GO Classes asked Feb 4, 2024
540 views
Memory Based GATE DA 2024 | Question: 22
Given the array \( [4, 3, 2, 1, 5] \), which of the following sorting algorithms can successfully sort the array in exactly two passes?Bubble SortInsertion Sort Selection...