Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal state is found, or it hits a node that has no children. Then the search backtracks and starts off on the next node.
From an algorithmic point-of view, all freshly expanded nodes are placed at the front of the search queue for expansion.
Space complexity of DFS is much lower compared to BFS (Breadth-first search). It also lends itself much better to heuristic methods of choosing a likely-looking branch.
Search Encyclopedia
|