Graph Traversal Part I

In this assignment, we will see how we can use Depth-First Search (DFS) and Breadth-First Search (BFS), which we learned about in previous lessons, to traverse a directed acyclic graph.

Depth-First Search (DFS)

With graphs, the most common DFS traversal is preorder traversal, so we'll focus on this. In the previous lesson on Binary Trees, we learned that we can perform DFS using either recursion or a stack.

We'll start with a solution using a stack, and then you can try implementing a recursive solution on your own.

// Implement a function `dfs` that accepts two arguments: the adjacency list
// representing a directed acyclic 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, []);
adjList.set(2, [1, 3, 4]);
adjList.set(3, [5]);
adjList.set(4, [6]);
adjList.set(5, []);
adjList.set(6, []);
adjList.set(7, [6]);

dfs(adjList, 2); // 2, 4, 6, 3, 5, 1 or 2, 1, 3, 5, 4, 6

// Note that the output can vary based on the order in
// which you process neighbors. These two outputs are
// the most likely, but other valid orders exist.

DFS Algorithm & Walkthrough

Let's look at our example graph.

While our algorithm will be similar to the algorithm we used to traverse a binary tree, we have a few interesting characteristics now that we're working with a graph. First, you'll notice that we can have a node with more than two neighbors. Node 2 has a pointer to nodes 1, 3, and 4. That means our algorithm must account for an unknown number of neighbors. Another new feature is that we can't necessarily reach every node in the graph. If we were to start our search at node 2, for example, there would be no way to reach node 7. In a binary tree, we can reach every child node from the root node. In a graph, we don't have a root node. Let's keep these differences in mind as we walk through our algorithm.

We want to process the vertices using preorder traversal. This means first processing the vertex (node)—in this case, printing its value—then traversing any of its outgoing neighbors.

So, we know what we need to do, but how do we implement it with a stack?

Before we process a node, we need to pop it from the stack and then add its neighbors to the stack. We repeat this process until the stack is empty.

Since the first node needs to be processed and our stack is initially empty, we start with the stack containing the given source node.

Let's write the algorithm:

• Start with the stack containing the first (source) vertex.
• Iterate until there are no elements left in the stack:
  • In each iteration, pop the element from the stack and process it (print it).
  • Iterate through the neighbors of the popped vertex and push those neighbor vertices to the stack.

Let's do a visual walkthrough using the graph above.

Step 1: We begin with the source vertex in the stack.

Step 2: In the first iteration, we pop a vertex from the stack, process it by printing it, and then add its neighbors to the stack. Based on our adjacency list and our algorithm saying we should iterate through our neighbors, we can infer the order in which we'll add our neighbors to the stack. First 1, then 3, and then 4.

Step 3: In the next iteration, we pop the top element in the stack, vertex 4, and process it by printing it. Then, we add its sole neighbor, vertex 6, to the stack.

Step 4: Now we pop vertex 6 from the stack and process it. Vertex 6 has no outgoing neighbors, so we're done with this step. Remember that this graph visualizes our adjacency list above, and vertex 6's neighbor list is empty.

Step 5: In the fourth iteration, we pop vertex 3 from the stack and process it. We push its only neighbor, 5, onto the stack.

Step 6: We pop the vertex 5 from the stack and process it. This vertex has no neighbors, so we continue.

Step 7: Finally, we pop vertex 1 from the stack. We process it by printing it. It doesn't have any neighbors, so we continue. However, now our stack is empty, so we've finished our traversal.

Implementation

Let's see the code implementation:

function dfs(adjList, source) {
  let stack = [source];
  while (stack.length !== 0) {
    let current = stack.pop();
    console.log(current);
    let neighbors = adjList.get(current);
    for (let neighbor of neighbors) {
      stack.push(neighbor);
    }
  }
}

DFS Recursive Solution

Try implementing the recursive solution on your own. Keep in mind that we first need to process the vertex before visiting other vertices. This should help you with the solution.

Again, it's important to note that multiple outputs are valid depth-first searches using preorder traversal. With our source node of 2, we can process our three outgoing neighbors in any order, so long as we explore that neighbor's entire depth before going to the next neighbor. The two most likely outcomes, based on our adjacency list, would be to process first 1 and its path, then 3 and its path, then 4 and its path, or, as we did in the walkthrough above, first 4, then 3, then 1.

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

Breadth-First Search (BFS)

In graphs, Breadth-First Search (BFS) is commonly used to explore vertices level by level, meaning that all vertices at the present depth are processed before moving on to the vertices at the next depth level.

We can perform BFS using a queue, which ensures that we process vertices in the order they are discovered.

Try implementing the solution on your own first. If you need help, refer to the walkthrough or the solution code.

// Implement a function `bfs` that accepts two arguments: the adjacency list
// representing an acyclic 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, []);
adjList.set(2, [1, 3, 4]);
adjList.set(3, [5]);
adjList.set(4, [6]);
adjList.set(5, []);
adjList.set(6, []);
adjList.set(7, [6]);

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

// Again, the order depends on which neighbor node we explore first

Walkthrough & Solution

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

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

    let neighbors = adjList.get(current);
    for (let neighbor of neighbors) {
      queue.push(neighbor);
    }
  }
}