Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Tree Structure
See the page on trees for an example of how we implement tree data structure in Javascript.
function Node (value) {
this.value=value;
this.left=null;
this.right=null;
}
Breadth First Search Algorithm
Recursion is the simpler way of implementing BFS because you don’t need to keep track of what’s left to visit.
The strategy to implement BFS algorithm is understanding what BFS is supposed to do. It goes down a path as far as possible first, then backtracks and repeats.
- Start at Root Node (or some arbitrary node if graph)
- Go through next level of tree
- Keep repeating down each level
- If graph, keep track of what’s been visited and skip that
BFS Recursive in Javascript – Binary Tree
You can’t use recursion for BFS. Well, you could but it won’t be pretty.
BFS Iterative in Javascript – Binary Tree
We want to travel down one branch until the end before backtracking. Below is the Javascript implementation of BFS.
function BFS (node) {
let queue=[node]; //FIFO: First In, First Out
while (stack.length>0) { //while stack isn't empty
const current=queue.shift(); //take from next item of stack (bottom of array)
//process current node
console.log(node.value);
if (current.left) {
stack.push(current.left); //add to queue
}
if (current.right) {
stack.push(current.right); //add to queue
}
}
}
Difference between BFS and DFS
Fundamentally, the difference between DFS and BFS is that with a DFS you push the children of the current node onto a stack, so they will be popped and processed before everything else, while for BFS you push the children onto the end of a queue, so they will be popped and processed after everything else.