V is a descendent of u if and only if there is an entirely undiscovered path from u to v at a certain step of this algorithm.
V is a descendent of u if and only if there is an entirely undiscovered path from u to v at a certain step of this algorithm. A strong relationship between antecedents and descendants and the nesting of intervals as determined by this algorithm is explained by the parenthesis structure of discovery and finishing times in this algorithm. Running this algorithm on a graph and then running it again on the transpose of the graph is one method to find (*) strongly connected components. Unlike a related algorithm, this one can find back edges. This algorithm can be implemented recursively or using a stack, unlike a related algorithm that uses a queue, and this algorithm was developed as a method to solve mazes. For 10 points, name this basic graph algorithm that goes as far as possible along one path before backtracking.
V is a descendent of u if and only if there is an entirely undiscovered path from u to v at a certain step of this algorithm.
depth first search [accept dfs; prompt on “search”; do not accept or prompt on “breadth first search” or “bfs”]