An algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level, i.e. a node with the minimal depth expanded first and on each level all possibilities are generated first and then solved.
An example: Order in which the nodes are expanded
Properties:
- Completeness: yes
- Optimality (Admissibility): yes
- Time Complexity: O(bd)
- Space Complexity: O(bd), b – branching factor, d – depth in the tree