Studying Graphs Pt.2: Breadth and Depth First Search

I'm building off a pervious blog post here about how to make an adjacency list and matrix in javascript, found here. I wanted to add onto this by putting these bad boys to use and doing some searching. I'll do what I did last time and split them up appropriately but refer to part 1 if you want a full description to get up and running just refer to the first part

Breadth First Search

The high level view of this search is to start at one node, then web out progressively layer by layer until you hopefully hit the desired node you're looking for. We start with our first node and then visit all its adjacent child nodes, checking whether it's the one we're looking for, and then proceeding to their child nodes if we haven't hit our stopping point.

A lower level psuedo-code of this would be:

1.) Initialize a queue with the starting node as the only element inside

2.) Create a while loop that runs until the queue is empty

3.) Pop off the first element in the queue and loop through all its children checking if any of these nodes are the one we're looking for

4.) If the child is not what we're looking for and we haven't seen it before, add this child node to the back of the queue

5.) Repeat until queue is empty

Adjacency List

This is the code that I came up with for my implementation:

const BFS = (start,end) => {
  const seen = new Set()

  const queue = [start]

  while( queue.length > 0) {

    const node = queue.shift()

    const children = list.get(node)

    for (let i = 0; i < children.length; i++) {

      if (children[i] == end) {
        return "There's a path!"
      } else {
        if (!seen.has(children[i])) {
          seen.add(children[i])
          queue.push(children[i])
        }
      }
    }
  }
  return "No path available!"
}

It's largely from the fireship.io reference I used in the first post. Using a set, we can keep track of the nodes we have seen so far. This way we don't fall into an infinite loop of visiting the same nodes over and over again. We push our starting node into the queue, start a while loop that continues until the queue is empty. Then we check all the children of the current node since our adjacency list is just a map data structure. If the child is not our end node, we check if the child is in the seen set. If it isn't we will add it to our seen set and into the back of the queue.

Adjacency Matrix

A matrix implementation is very similar but how we index and find out what edges are connected to the current node is different. Take a look at my implementation:

const BFS = (start, end) => {
  const seen = new Set()

  const queue = [start]

  while (queue.length > 0) {
    const node = queue.shift()

    if (matrix[node][end] == 1) {
      return "There's a path!"
    }

    for (let i = 0; i < matrix[node].length; i++) {

      if (matrix[node][i] == 1) {
        if (!seen.has(i)) {
          seen.add(i)
          queue.push(i)
        }
      }
    }
  }
  return "No path avaliable"
}

In a matrix implementation, we can immediately check if the current node is connected with the ending node by checking the right index at "matrix[node][end] == 1"

If there isn't a 1 there, we'll cycle through all the elements in this sub-array, checking if the values are 1 indicating an edge. If it is a 1, then we do exactly as the list implementation, checking if the node is in the seen and adding it to the queue and set if not.

Depth First Search

Moving on, the next big search algorithm is depth first search which is really useful for finding if paths exist between nodes quickly or even in binary search trees to output min or max values. It's very common for this type of search to make use of recursion. The high level view is that we start at a node, and go as far into the tree by hopping from child to child until we reach no new points and back track doing the same to nodes we've passed by. It's important to make use of a set to keep track of what we've seen already.

Adjacency List

This is a naturally more difficult algorithm to grasp than BFS since its kind of shrouded in recursive mystery.

const DFS = (start, end, seen = new Set()) => {

  seen.add(start)

  const children = list

  for (let i = 0; i < children.length; i++) {
    if (children[i] == end) {
      return "There's a path"
    } else {
      if (!seen.has(children[i])) {
        return DFS(children[i], end, seen)
      }
    }
  }
  return "No path available!"
}

At each recursive step we have a new starting node, we loop through the children of the node checking if this is the one we want. If it is we win! If not we call the same function on the child node making it the new start node and pass in our seen set of nodes we've already visited.

Adjacency Matrix

const DFS = (start, end, seen = new Set()) => {

  seen.add(start)

  if (matrix[start][end] == 1) {
    return "There's a path!"
  }

  for (let i = 0; i < matrix[start].length; i++) {
    if (matrix[start][i] == 1) {
      if (!seen.has(i)) {
        return DFS(i, end, seen)
      }
    }
  }
  return "No path available"
}

The only difference between the matrix and the list code for a DFS is that we'll index first check if the node we're on has a one at location for the end node. If not, then we'll loop through all the entries, checking if there's a one for that edge and if the seen set does not contain that child. If so, we'll call DFS again on that child.

I hope this has been helpful. The really nice thing about adjacency lists and matrices is how easy they can get up and running for you to practice those good old interview questions.

Let me know if you have any questions