Graph Traversal with BFS - Code (JavaScript)

Data can be stored in data structures like graphs and trees. Technically trees are graphs as we will see in the implementation below.

Graph

Graphs are used to describe a model that shows the route from one location to another. A graph consists of a set of nodes and edges. An edge is a pair of nodes that are connected. A path is used to describe traveling between nodes that share edges.

Trees
A tree, on the other hand, is a collection of nodes. There is a root node otherwise called 'Head'. The nodes can then have children nodes thus flowing in a hierarchy manner.

The most common implementation of graphs is finding a path between two nodes, finding the shortest path from one node to another and finding the shortest path that visits all nodes.

The traveling salesman problem is a great example of using a tree algorithm to solve problem.

Breadth-First Search is among the common graph or tree traversal algorithm techniques used to solve such problems.

Below is an implementation of the BFS algorithm that takes in a graph in form of an Adjacency Matrix and a root node (number) then return the length of other nodes from it. It's used to find distances between nodes on a graph, which henceforth can be used to find the shortest distance.

Here's the graphical representation of the graph:

Here's the code:

let bfs = (graph, root) => {
  let nodesLen = {};

  for(let i = 0; i < graph.length; i++){
    nodesLen[i] = Infinity; // Idicates that a node is not reachable from the start node
  }
  nodesLen[root] = 0; // The distance of the root node from the root node is set to 0

  let queue = [root] // Keep track of nodes we visit
  let current; // Keep track of the current node we are traversing

  // This loop will keep traversing nodes in the queue until we have no other node to traverse
  while(queue.length != 0){
    current  = queue.shift() // Removes the first element in the array

    let curConnected = graph[current] // We get all the nodes connected to the current node
    let neighborIdx = []
    let idx = curConnected.indexOf(1) // Gets the index of the first node connected to the current node because the number one in our array shows that the node is connected to anothe node on that index

    // If there is no node at the index of one, the index variable will be set to -1. 
    while(idx != -1){
      neighborIdx.push(idx) // So while index does not equals to -1, push our index onto our list of neighbors.
      idx = curConnected.indexOf(1, idx + 1) // This line searches for the next connected node.
    }

    // Now that we know all the nodes connected to the current node, we loop through this connected nodes, and get the distance
    for ( let j = 0; j < neighborIdx.length; j++){
      if (nodesLen[neighborIdx[j]] == Infinity){ // This line we haven't set the distance from the nodesLen[neighborIdx[j]] yet so we will set now. 
        nodesLen[neighborIdx[j]] = nodesLen[current] + 1
        queue.push(neighborIdx[j]) // We push the neighbor to the queue so the next time we go through the while loop, we will check the neighbors of that node too.
      }
    }
  }

  return nodesLen
}

let exBFSGraph = [
  [0,1,1,1,0],
  [0,0,1,0,0],
  [1,1,0,0,0],
  [0,0,0,1,0],
  [0,1,0,0,0]
]

bfs(exBFSGraph, 1)

Blog

Graph Traversal with BFS - Code (JavaScript)

Clint Maruti

Join Our Newsletter. No Spam, Only the good stuff.

Related