Data Structures and Algorithms in JavaScript: Breadth First Search (BFS), Depth First Search (DFS)

Both algorithms are used for Tree and Graph traversal.

1. Breadth First Search (BFS)

BFS explores the graph/tree level by level, starting from the given source node. It uses a queue to keep track of the nodes to be visited next.

class Graph {
  constructor() {
    this.adjacencyList = new Map()
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, [])
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList.get(vertex1).push(vertex2)
    this.adjacencyList.get(vertex2).push(vertex1) // For an undirected graph
  }

  bfs(startingNode) {
    const visited = new Set()
    const queue = []

    visited.add(startingNode)
    queue.push(startingNode)

    while (queue.length > 0) {
      const currentNode = queue.shift()
      console.log(currentNode)

      const neighbors = this.adjacencyList.get(currentNode)
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor)
          queue.push(neighbor)
        }
      }
    }
  }
}

// Example usage:

const graph = new Graph()

// Adding vertices
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")

// Adding edges
graph.addEdge("A", "B")
graph.addEdge("A", "C")
graph.addEdge("B", "D")
graph.addEdge("C", "E")

// Perform BFS starting from node "A"
console.log("Breadth First Search starting from node A:")
graph.bfs("A")

// Graph visualisation:
//    A
//   / \
//  B   C
//  |   |
//  D   E

// Output:
// A
// B
// C
// D
// E

2. Depth First Search (DFS)

DFS explores the graph/tree as far as possible along each branch before backtracking, starting from the given source node. It uses a stack.

class Graph {
  constructor() {
    this.adjacencyList = new Map()
  }

  addVertex(vertex) {
    this.adjacencyList.set(vertex, [])
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList.get(vertex1).push(vertex2)
    this.adjacencyList.get(vertex2).push(vertex1) // for an undirected graph
  }

  dfs(startingNode) {
    const visited = new Set()

    const explore = (node) => {
      if (visited.has(node)) {
        return
      }

      console.log(node)
      visited.add(node)

      const neighbors = this.adjacencyList.get(node)
      for (const neighbor of neighbors) {
        explore(neighbor)
      }
    }

    explore(startingNode)
  }
}

// Example usage:

const graph = new Graph()

// Adding vertices
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")

// Adding edges
graph.addEdge("A", "B")
graph.addEdge("A", "C")
graph.addEdge("B", "D")
graph.addEdge("D", "E")

// Perform DFS starting from node "A"
console.log("Depth First Search starting from node A:")
graph.dfs("A")

// Graph visualisation:
//     A
//    / \
//   B   C
//   |
//   D
//   |
//   E

// Output:
// A
// B
// D
// E
// C