Hello Hello, Le’ts continue from the last section where we looked at graphs and their representations. Today we will look at Graph Traversal, If you have been following the previous sections then you will agree with me we had a look at what traversal was in binary trees. Same ways Graph traversal is the process of visiting each node/Vertex in a Graph Data Structure and here as well we will discuss two ways BFS (Breadth First Search) and DFS (Depth First Search) graph traversal.

In any of the Traversal methods the paramount process will be to keep track on any Vertex visited and those not visited and if already visited then we move to the next one, moving to the next one comes in different style or is achieved with different strategies which are separated in the two mentioned type of traversal

DFS will be the process which involves visiting a vertex and there after continuing visiting further it’s vertices until there is no more to visit and resume back to other unvisited Vertices. in Graph DFS it is appropriate to use a Stack that will serve as a check point to verify each Vertex has been visited already and then removing from the top stack by popping the last element out. the re several ways to achieve a graph DFS we can equally employ the help of a Deirect AdjacentList as out stack for the same process without creating any other variable to hold and track already visited and this method may need a Recursive process to be implemented. Let’s take a look at both cases by running the recursive method first before the one which involves a new Stack with an iterative method.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }
  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
  DFS_Recursive(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    })(start);

    return result;
  }
  DFS_FirstIterative(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    let currentVertex;

    visited[start] = true;
    while (stack.length) {
      currentVertex = stack.pop();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
  }
}

let g = new Graph();

g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addVertex('E');
g.addVertex('F');

g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
g.addEdge('D', 'E');
g.addEdge('D', 'F');
g.addEdge('E', 'F');

//          A
//        /   
//       B     C
//       |     |
//       D --- E
//           /
//          F

// QUEUE: []
// RESULT: [A, B, C, D, E, F]


console.log(g.DFS_FirstIterative('A'));
console.log(g.DFS_Recursive('A'));

These two are actually not too difficult to implement as seen above after creating some vertices and edges based on the graph structure we have bellow, we only need to figure out which type of DFS we are dealing with and in the case of DFS_Recursive we use the direct adjacencyList as our linked-list and create our dfs recursive method to handle the case where after visiting a vertex we keep going down until there is no more nodes to explore before coming back to the next one. The same process is involved in the case of DFS_FirstIterative but this time around we create a new stack from scratch to handle the iteration based on its length while we keep popping out each visited and explored vertex. Notice that there is no recursion here.

BFS in the hand will be dealing with the process of visiting each vertex and trying to explore all it’s adjacent links before engaging with any further unvisited nodes. in this case if a vertex has 3 connections to other Vertex which are in turn connected to other BFS will visit all those 3 nodes before coming back to any other unvisited nodes in the graph, let’s have a look

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }
  removeVertex(vertex) {
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
    
  BFS_(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex;
    visited[start] = true;

    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
  }
}

let g = new Graph();

g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addVertex('E');
g.addVertex('F');

g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
g.addEdge('D', 'E');
g.addEdge('D', 'F');
g.addEdge('E', 'F');

//          A
//        /   
//       B     C
//       |     |
//       D --- E
//           /
//          F

// QUEUE: []
// RESULT: [A, B, C, D, E, F]

console.log(g.BFS_('A'));

BFS is more or less similar to the iterative DFS but the visiting and exploring logic are different as I touched on in both cases above, you can try to use the following diagram to read meaning out of my baby explanation about the two situations above
ie. DFS will go down from A-D branching to E,C before F without worrying about
where BFS will explore from A-B come back to C and continue from D-E and F.

I hope the above does a little more justice to the the topic in case it doesn’t seem click yet but eventually it will, kindly keep trying. On this note I will see you in the next 🙂