# Depth First vs. Breadth First Search It is worth noting that Depth First Search and Breadth First Search are general techniques towards **searching**. They are *not* simply used with graphs. They could be used when finding edit distance between strings, graphs, etc. This is a great example of where [Geometry](Geometry.md) really comes into play (/posts/see [Shape](Shape.md)). We can state generally: > **Depth First Search** and **Breadth First Search** are great for searching *relationships*. From the Algorithm Design Manual, it is stated: > BFS and DFS provide mechanisms to visit each edge and vertex of the graph. They prove the basic of most simple, efficient graph algorithms. It is worth noting even further that DFS and BFS are both useful due to how they *organize* a graph structure. They both organize it is as a type of tree. The resulting (different) trees have a set of constraints that make them easier to work with, search, explore, analyze, etc. Put another way, both DFS and BFS find a new way to [represent](Big%20Idea%20Representation.md) our graph. ### [Depth-First-Search](Depth-First-Search.md) **Data structure**: Depth First Search use a **stack**. A stack has **last in first out (LIFO)**. It either can be a stack that we create (in the case of a while loop implementation) or it can be a stack that uses recursion. **Use cases:** One of the best use cases is for topological sorting of a graph. Depth first search is used when we want to implement *back tracking*, complete search, finding all possible paths, etc. Depth first search goes **deep**; it goes deep into a path, explores all of it, and then decides whether to go on to another path. **Time complexity**: $O(n + m)$, *linear* ### [Breadth First Search](Breadth%20First%20Search.md) **Data structure**: Breadth First Search on the other hand is implemented iteratively with a **queue**. A queue has **first in first out (FIFO)**. Breadth First Search is great to check *if there is a path* between two nodes. It moves out *layer by layer*. **Use cases:** Find the shortest path between on vertex and all other vertices, compute connected components. **Time complexity**: $O(n + m)$, *linear* **Notes**: From a geometric perspective, consider a graph with radius 5 (/posts/see [Shape](Shape.md)). If we start at some node `A`, we will first look at all of its neighbors of distance `1` away (this is the exploration of the first "layer"). Then we will look at the neighbors of distance `2` (the second layer). And so on. We slowly increase the distance from our start node and give us breadth. ### A note on the differences... From the Algorithm Design Manual, it is stated: > The difference between BFS and DFS results is in *the order* in which they explore the vertices. This order depends completely upon the *container data structure* used to store the `discovered` (but *not* `processed`) vertices. ### A note on the similarities We see that the time complexity is $O(n + m)$ for both algorithms. My first impression was how is that so? Well, a nice way to think about it is from the *data structure* perspective. Our graph can be structured as an adjacency list. This structure has $n$ nodes and $m$ edges. It will be stored as: ```python g = { "a": ["b", "d", "x"], "b": ["c", "d", "q", 'e'], ... } ``` So below we can think of it as having $n$ keys, and the total length of all of the list values is $m$. In order to fully explored the graph we need to traverse this entire structure. The fastest way that is physically possible to traverse this entire structure would run in $O(n + m)$. And thankfully that is the case for both DFS and BFS. --- Date: 20211013 Links to: [Graph-Algorithms](Graph-Algorithms.md) [Computer Science MOC](Computer%20Science%20MOC.md) Tags: References: * [Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms](https://www.youtube.com/watch?v=TIbUeeksXcI) * Algorithm Design Manual, Chapter 5: Graph Traversal