Graph Theory37 sections · 1633 units
Open in Course

Discovery Time

(When DFS first visits vertex)

Discovery time disc[v] is the timestamp when DFS first visits vertex vv. The first vertex visited gets disc[v] = 0, the next gets 11, and so on. Discovery times create a total order on vertices based on when DFS reaches them.

If uu is an ancestor of vv in the DFS tree, then disc[u] < disc[v]. But the reverse is not always true. A node discovered earlier might be in a different subtree, not an ancestor. To confirm ancestry, you also need the finish time: uu is an ancestor of vv if and only if disc[u] < disc[v] < fin[u].