information:extraction, linguistic:voice_change, stylistic:tone
Complexity

The computational complexity of DFS was investigated by John Reif. More precisely, given a graph G {\displaystyle G}, let O = (v 1, …, v n) {\displaystyle O=(v_{1},\dots,v_{n})} be the ordering computed by the standard recursive DFS algorithm. This ordering is called the lexicographic depth-first search ordering. John Reif considered the complexity of computing the lexicographic depth-first search ordering, given a graph and a source. A decision version of the problem (testing whether some vertex u occurs before some vertex v in this order) is P -complete, meaning that it is "a nightmare for parallel processing ".

A depth-first search ordering (not necessarily the lexicographic one), can be computed by a randomized parallel algorithm in the complexity class RNC. As of 1997, it remained unknown whether a depth-first traversal could be constructed by a deterministic parallel algorithm, in the complexity class NC.