BFS & DFS


Breadth-first and Depth-first Search are two navigation methods that involve searching through graph trees, and finding a path through these data points, from Start node to Target node. Breadth-first Search (BFS) involves a data structure called a "queue," which utilizes a First-in, First-out (FIFO) approach to searching through data nodes. This creates a search method that expands all possible next locations (children nodes), before examining any of the further possible locations (grandchildren nodes). Once the BFS has found the Target node, it is able to trace back the most efficient path to the Start node. However, this search method can take much longer than Depth-first Search in most situations. Depth-first Search (DFS) takes the opposite approach to searching, by utilizing a data structure called a "stack," which utilizes a Last-in, First-out (LIFO) approach to node searching. The use of the stack creates a search method that expands the first possible next location (child node), and then keeps expanding down a singular line of the first possible next location that it finds. Once the DFS has found the Target node, it traces back the path that it used to get to the Target node from the Start node. This means that DFS is able to have much faster searching in most situations, but it is not always the most efficient path from Start to Target. This difference causes BFS to be much more reliable, and much more widely-used for navigation purposes. For more information on BFS and DFS, and to see how to implement these methods into code, check out my tutorial.