In the following graph, discovery time stamps and finishing time
Duration: 5 min
2015
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as 𝑥/𝑦, where 𝑥 is discovery time stamp and 𝑦 is finishing time stamp.
It shows which of the following depth first forest?
- A.
{a,b,e} {c,d,f,g,h}
- B.
{a,b,e} {c,d,h} {f,g}
- C.
{a,b,e} {f,g} {c,d} {h}
- D.
{a,b,c,d} {e,f,g} {h}
Attempted by 126 students.
Show answer & explanation
Correct answer: A
Key idea: in a DFS, a vertex u is an ancestor of vertex v in the DFS forest exactly when discovery(u) < discovery(v) and finishing(v) < finishing(u). Use interval nesting of (discovery/finish) to find the trees.
Intervals (discovery/finish) for each vertex: c 1/10, g 2/7, f 3/4, h 5/6, d 8/9, b 11/16, e 12/15, a 13/14.
Tree rooted at c: c's interval 1–10 contains g (2–7). g contains f (3–4) and h (5–6). d (8–9) is also inside c. Hence this tree is {c, g, f, h, d}.
Tree rooted at b: b's interval 11–16 contains e (12–15), which contains a (13–14). Hence this tree is {b, e, a}.
Conclusion: The DFS forest consists of the two trees {a, b, e} and {c, d, f, g, h}.
A video solution is available for this question — log in and enroll to watch it.