In the following graph, discovery time stamps and finishing time stamps of…
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.