Graph search
= Graph search
A <graph search> explores vertices through incident edges while recording visited vertices. On a finite <graph>, depth-first or breadth-first exploration terminates and decides <reachability>; recording predecessors also gives a path. Restricting to vertices reachable from a start and able to reach an accepting vertex identifies the productive part of a <deterministic finite automaton>.