In the context of finding bridges in a connected undirected graph using…
2025
In the context of finding bridges in a connected undirected graph using Depth-First-Search (DFS), an edge (u, v) is identified as a bridge. Which of the following conditions hold true?
(Here pre [ ] holds pre-order traversal numbering of the node. low [ ] holds the lowest pre-order of any vertex connected to node.)
- A.
low [v] < pre [u]
- B.
low [v] > pre [u]
- C.
low [v] < low [u]
- D.
pre [v] == pre [u]
Attempted by 85 students.
Show answer & explanation
Correct answer: B
For a tree edge (u, v), it is a bridge if low[v] > pre[u]. This means no back-edge connects the subtree at v to u or its ancestors.