Breadth-First Search vs. Depth-First Search
Traversing thru graphs or trees is very common in computer science, even software engineering in order to build scalability without losing a step in time complexity. Whether your attempting to get the shortest path between two points(BFS), or exploring the nodes and edges of a graph(DFS), these techniques become critical in solving everyday use cases. Lets look at how these algorithms can better help us traverse, and also understand the difference and similarities of the two.
Breadth-First Search
First lets look at BFS. A Breadth-First Search uses a Queue data structure,(placing each node into a queue) starting at an arbitrary point with-in the graph or tree, as it begins to traverse thru each node while checking its neighboring nodes. Once the current node is done being checked, it moves thru the queue until making its way down the stack. This type of search has become ideal for finding the shortest path, using Dijkstra’s algorithm allows us to iterate on top if this type of traversal, by allowing us to find the shortest path between two points. As you can see from the picture below we can use this to help identify the best way to get thru the graph using Dijkstra’s.
Depth-First Search
Now that we got a look at BFS, lets see its counter. Depth-First Search uses a stack data-structure,(collection of elements) starting at some arbitrary point, traversing thru a graph or tree as far as possible before needing to backtrack. This makes it ideal for completing solutions that are farther from the original source. Below shows good use case for this type of search, traversing thru a maze.
In this example, if the player was attempting to make it thru, and they had hit a wall, they would then need to backtrack to the node(arrow in above case)in order to continue thru the maze eventually making it to the end. With DFS, this algo requires you to backtrack up the graph(or tree) in order to continue.
In contrast Breadth-First Search works well with something like the ghost in Pacman. These ghost are traversing thru the nodes in the graph, exploring each node in that layer, before moving on to the next. Making it ideal for search and destroy for our little yellow friend. Each of these algorithms have there place, depending on what your looking to achieve its best to take in consideration each of there up and downs(pun intended!).
Speed Test
As far as speed? well that seems debatable at the very least in Computer Science circles, depending on what task your trying to complete. The general consensus seems to be that because DFS does not need to keep track of nodes in the queue in memory, this in turn makes it quicker in the end. Again I feel this comes down to what are you trying to achieve? Are you attempting to get the shortest point from one node to the next and not worried about space in memory? use BFS, otherwise you can use DFS if your looking to save space in memory but get to your desired outcome. Below I listed a great comparison graph from GeeksforGeeks, and a couple Youtube video’s from user WilliamFiset that I fought extremely helpful.
Happy Algo-ing!
