breathFirstSearch

breathFirstSearch.js

function Node(value){
  this.value = value
  this.left = null;
  this.right = null;
}

Node.prototype.toString = function() {
  return this.value;
}  

Node.prototype.breathFirstTraversal = function breathFirstTraversal(rootNode) {
    if (rootNode === null) {
    return;
  }
  
  // Create our queue and push our root node into it.
  var queue = [];
  queue.push(rootNode);
  
  // Continue searching through as queue as long as it's not empty.
  while (queue.length > 0) {
    // Create a reference to currentNode, at the top of the queue.
    var currentNode = queue[0];
    
    // If currentNode has a left child node, add it to the queue.
    if (currentNode.left !== null) {
      queue.push(currentNode.left)
      console.log(queue)
    }
    // If currentNode has a right child node, add it to the queue.
    if (currentNode.right !== null) {
      queue.push(currentNode.right)
      console.log(queue)
    }
    // Remove the currentNode from the queue.
    queue.shift()
  }
}

This is a recursive algorithm used for searching graph data structures. It selects a node as a starting point and visits all neighbouring nodes of the same depth as the starting node before going to the next depth level. It continues this process until it reaches the last node in the graph. BFS is implemented using a queue data structure

Applications of BFS

• Finding the shortest path in an unweighted graph: In an unweighted graph, the shortest path is the path with the least number of edges. This is because with BFS we always reach a vertex from the root using a minimum number of edges.
• GPS Navigation Systems: BFS can be used to find all the neighbouring locations for a given location.
• Social Networking Websites: In social networks, BFS can be used to find all the people that are at a distance k from a user. Where k is the number of levels in the graph.
• Peer to Peer Networks: In peer to peer networks, BFS can be used to find all the neighbour nodes to a given node.