Grokking Algorithms in JavaScript - Part 2

This is part 2 in a series of articles about the algorithms covered in Aditya Y. Bhargava's excellent book Grokking Algorithms. In Part 1 I looked at binary search, selection sort and quicksort. In this part I will look at graphs and one of their associated algorithms.

Breadth-first search

Breadth-first search ("BFS") is a means of searching through the nodes in a graph to find a node that has specific properties: eg. find a route from town A to town B, or; find a certain person in your social network.

Given a graph, a start node and an end node, BFS can answer 2 questions:

1. is there a path from start to end, and
2. what is the shortest path (in terms of the number of nodes visited) from start to end

So what exactly is a graph?

Graphs in this context don't have x and y axes: we're not talking about line graphs or bar charts. The graphs that we are talking about here are representations of connections in a network.

A graph is made up of nodes which are connected by edges. For example, a graph might be a representation of a geographical area where nodes are towns and edges are the roads that connect them. Or it might represent a social network where nodes are people and edges represent the relationships between them.

Our example graph

The picture below shows a small social network with your immediate connections, their connections and their connections' connections; so, three levels of connection.

Imagine that your central heating boiler has broken down and you want to know if your social network contains a heating engineer. You also want to find the heating engineer that is closest to you in the network.

Before getting into the workings of BFS it's worth thinking about how we are going to represent the graph to be searched. Indeed, a lot of the work in writing graph algorithms is in constructing the graph representation in the first place. The perfect data structure for the job is a hash table and the Grokking Algorithms book devotes an entire chapter to the subject (which is well worth a read). In simple terms, a hash table stores data in key value pairs where keys are unique and values can hold any type of data, including arrays or even other hash tables.

Python and JavaScript each has a native data structure that performs the job of a hash table: Python has its Dictionary data structure while in JavaScript we can use the Map() object.

Representing the graph as a JavaScript Map() object

const graph = new Map();
graph.set("you", [
  {name: "peter", job: "bricklayer"},
  {name: "dimitrios", job: "chef"},
  {name: "katie", job: "architect"}
]);
graph.set("peter", [
  {name: "dean", job: "solicitor"},
  {name: "aleksandra", job: "doctor"},
]);
graph.set("dimitrios", [
  {name: "sam", job: "heating engineer"},
  {name: "shefali", job: "driving instructor"}
]);
graph.set("katie", [
  {name: "shefali", job: "driving instructor"}
]);
graph.set("dean", [
  {name: "james", job: "graphic designer"},
]);
graph.set("aleksandra", []);
graph.set("sam", [
  {name: "molly", job: "software engineerr"},
]);
graph.set("shefali", [
  {name: "andrew", job: "heating engineer"},
  {name: "amy", job: "barrister"},
]);
graph.set("james", []);
graph.set("molly", []);
graph.set("andrew", []);
graph.set("amy", []);

BFS methodology

A quick glance at the image of our small social network above tells you that there are 2 heating engineers in this 3-level network - Sam & Andrew - and that Sam is the nearest connection to you being a level 2 connection whereas Andrew is level 3. But how do you code that into an algorithm?

BFS works by processing all closest connections to a node before moving on to the next closest connections, and so on. The way to enforce that "closest first" rule is to use a queue. A queue data structure works just the same as a queue in real life: people join the queue at the back and leave when they get to the front.

So starting with the "you" node in the graph, the algorithm adds the "you" node's neighbours to the back of the queue. To find the neighbours of a node simply look up that node in the graph hash table. Remember that a hash table is a collection of key/value pairs. In the graph hash table the node is the key and its associated value is an array of the node's neighbours.

The algorithm looks at the queue, removes the person from the front and checks whether they are a heating engineer. If so, the search is over - return that person's name. Otherwise add that person's neighbours to the back of the queue, take the person from the front and continue.

This process repeats until:

a. you find a heating engineer, or
b. the search queue is empty - which means there is no heating engineer in your social network.

It's worth highlighting again here that the First In First Out (FIFO) nature of a queue means that 1st level connections are processed before 2nd level connection; 2nd level connections are processed before 3rd ... and so on. This guarantees that a search for a heating engineer in the above graph will always return Sam, not Andrew, ie: the shortest path.

There is another important aspect to think about here. Have a look at the image above showing the social network. You will note that Shefali is a connection of Dimitrios and Katie. We don't want to add Shefali (and by extension her connections) to the search queue twice. To avoid that happening we can keep a list of people we have already considered. And at the stage above where a person is added to the back of the queue, that needs only happen if that person isn't in the "already processed" list. In the code below that list takes the form of a simple array called searched.

The code that implements the steps above is as follows. This is based on the example in Grokking Algorithms, extended a little and converted to JavaScript. The search function takes two parameters: the start node ("you" in this case) and the job to search for. It searches the graph data structure set out above.

function search(name, job) {
  let searchQueue = graph.get(name);
  const searched = [];
  while (searchQueue.length > 0) {
    const person = searchQueue.shift();
    if (!searched.includes(person)) {
      if (person.job === job) {
        console.log(`${person.name} is a ${job}`);
        return true;
      } else {
        searchQueue = searchQueue.concat(graph.get(person.name));
        searched.push(person);
      }
    }
  }
  console.log(`Nobody in your social network is a ${job}`);
  return false;
}

search("you", "heating engineer"); // "sam is a heating engineer"
search("you", "police officer"); // "Nobody in your social network is a police officer"

Summary

In this article I have introduced the concept of graphs and how to use a hash table to represent a graph in code, specifically using the Map() structure in JavaScript. I have laid out the steps that a BFS algorithm takes to traverse a graph in search of a node with certain properties and demonstrated how such an algorithm might be implemented in JavaScript.

In the next article in this series I will build on the concept of graphs, introduce the idea of weighted graphs and take a look at another graph traversal algorithm called Dijkstra's algorithm.

Cover image by Denys Nevozhai on Unsplash