Depth-First Search and Breadth-First Search Fundamental Difference

Depth-First Search is probably the fundamental graph traversal or tree traversal algorithm. It is used in many different questions including questions that seem like they’re unrelated to graphs, but can actually be turned into graph problems. We can think of it like a tree structure, and you have to traverse through its leafs (Nodes), find connections to other leafs, backtrack when you run out of paths, and repeat the process until all leafs are accounted for. These nodes can be any type of data, like Strings and Numbers.

Breadth-First Search is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbors nodes at the present depth prior to moving on to the nodes at the next depth level.

The fundamental difference between these two is the order in which you traverse child nodes. Let’s say we have one node (A) and A has reachable paths to other nodes (B and E).

In a Depth-First Search approach, you would put A in the stack first and then add a child node, B, on top of the stack. Then you would visit all of B’s children. Add them to the top of the stack and repeat the process until you ran out of paths to take then remove the top most node in the stack.

If you want to learn more about Depth-First Search, I wrote a much in depth explanation on it and also discuss the idea of Strongly Connected Components. https://devjoe.medium.com/strongly-connected-component-fa0449b16ce0

With Breadth-First Search you do the opposite, you would use a queue instead of a stack. In our example, if we were to start at A we would add B and E to the queue because they are child nodes to the current node that we are on(*).

Then we grab the first node in the queue, B, remove it and grab all of its child nodes and add them to the end of the queue. You repeat the process until you reach all vertices.

The difference between a stack and queue is a stack is where you grab the last element you added and a queue where you grab the first element you added. An easy one you can remember this is, Stack — Last In, First Out. Queue — First In, First Out.