Graph Traversal Part II

In one of the previous assignments, we learned how to traverse a directed acyclic graph.

However, what if we have a directed cyclic or undirected graph? Can we do the same thing as before? Let's see.

// Implement a function `dfs` that accepts two arguments: an adjacency
// list representing an undirected graph, and a starting vertex (source).
// The function should print the vertices in preorder depth-first
// traversal order.

function dfs(adjList, source) {
  // implementation goes here
}

const adjList = new Map();
adjList.set(1, [2]);
adjList.set(2, [1, 3]);
adjList.set(3, [2]);

dfs(adjList, 1); // 1, 2, 3

Let's start by looking at what would happen if we used the recursive dfs function from the Graph Traversal Part I assignment:

function dfs(adjList, source) {
  console.log(source);
  let neighbors = adjList.get(source);
  for (let neighbor of neighbors) {
    dfs(adjList, neighbor);
  }
}

Walkthrough

Let's do a step-by-step visual walkthrough using the graph below as an example:

Step 1: In the first call to dfs, we pass adjList and 1 as arguments, logging the value 1. With each call to dfs, we get a new list of neighbors we need to process. To help keep track of our progress, we'll write the neighbors next to our call stack in orange. Once we finish processing all of the neighbors for a given call, we've finished that call and can pop it from the stack.

For vertex 1, we have vertex 2 as our neighbor that needs processing. We invoke dfs recursively, passing adjList and 2, the first neighbor. This adds another call to the stack.

Step 2: In our new invocation of dfs, we've passed adjList and 2 as arguments, logging the value 2. After that, we call dfs recursively again, passing adjList and the first neighbor vertex of 2, vertex 1.

Step 3: In the third call to dfs, we pass adjList and 1 as arguments, logging the value 1. Then, we call dfs again, passing adjList and the first neighbor vertex of 1, which is vertex 2.

Are you seeing the problem? We are continuously alternating between calls to dfs with the second argument being 1 and 2. This back-and-forth traversal will ultimately cause a stack overflow.

So what is the solution? We need a way to track the vertices we've visited, and one convenient way to do this is by using a set.

We'll create a set called visited to track the visited vertices, allowing us to check in constant time whether a vertex has already been visited. If it has, we won't call the dfs function with that vertex as the second argument again.

Let's do another walkthrough, now with a set:

Step 1: In the first call to dfs, we pass adjList and 1 as arguments, logging the value 1. Then, we add vertex 1 to a set visited and call the dfs function, passing adjList and the first neighbor vertex of 1, which is 2.

Step 2: In the second call to dfs, we log the value 2 and add vertex 2 to the set visited. After that, since vertex 1 is the first neighbor but is already in the set, we skip it and call dfs passing adjList and the second neighbor of vertex 2, which is vertex 3.

Step 3: In the third call to dfs, we log the value 3 and add it to the visited set. After that, since vertex 2 is the first neighbor but is already in the set, we skip it. There aren't any more neighbors, so this function returns undefined and we pop it from the stack.

Step 4: We are back in the second function call. We already checked the first neighbor, so we can continue on to neighbor 3. 3 is present in visited, meaning that all of our neighbors have been processed, and we can pop this function call from the stack.

Step 5: Finally, back in the first function call, we have visited the only neighbor, so our function returns undefined and we can pop it from the stack.

Recursive Solution

function dfs(adjList, source, visited = new Set()) {
  console.log(source);
  visited.add(source);

  let neighbors = adjList.get(source);
  for (let neighbor of neighbors) {
    if (!visited.has(neighbor)) {
      dfs(adjList, neighbor, visited);
    }
  }
}

Alternative Solutions

Try implementing a solution using a stack data structure and a visited set.

function dfs(adjList, source) {
  let stack = [source];
  let visited = new Set([source]);

  while (stack.length !== 0) {
    let current = stack.pop();
    console.log(current);

    let neighbors = adjList.get(current);
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

Now, try refactoring the breadth-first search solution using a visited set on your own.

// Implement a function `bfs` that accepts two arguments: the adjacency list
// representing an undirected graph and a starting vertex (source).
// The function should print the vertices in breadth-first
// traversal order.

function bfs(adjList, source) {
  // implementation goes here
}

const adjList = new Map();
adjList.set(1, [2, 3]);
adjList.set(2, [1, 4]);
adjList.set(3, [1, 4, 5]);
adjList.set(4, [2, 3]);
adjList.set(5, [3, 6]);
adjList.set(6, [5]);

console.log(bfs(adjList, 1)); // 1, 2, 3, 4, 5, 6 or 1, 3, 2, 5, 4, 6

function bfs(adjList, source) {
  let queue = [source];
  let visited = new Set([source]);

  while (queue.length !== 0) {
    let current = queue.shift();
    console.log(current);

    let neighbors = adjList.get(current);
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}