Depth First Search

#uninformed

  1. Start with the first reachable state
  2. Move to that state's first reachable state that hasn't been discovered yet
  3. Move to that state's first reachable state that hasn't been discovered yet
  4. If we reach a dead end move backwards until you have more states to search
  • Def. Newly found states are put at the top of the priority queue
  • Not complete because of indefinite paths or depth limit
  • But is memory efficient

For infinitely deep search spaces (or just large ones) a depth limit can be set.

Session 3 - DFS Example.png#invert

DFS Forest

Excerpt modified from University of Edinburgh

A DFS starting at some vertex explores the graph by building up a tree that contains all vertices that are reachable from and all edges that are used to reach these vertices. We call this tree a DFS tree.

A complete DFS exploring the full graph (not only the part reachable from the given vertex ) builds up a collection of trees (trees reachable from various starting points), or a forest, called a "DFS forest".

DFS-Forest Component

A DFS-Forest Component then is simply one Strongly Connected tree inside of this forest. See: StackOverflow