Breadth First Search

BFS is an algorithm for traversing Graph data structures. It starts at some arbitrary node of a graph and explores the neighbour nodes (which are at current level) first, before moving to the next level neighbours.

See it in action:

Code algorithm

For BFS, we utilise queue data structure to help with the operations.

type Node = {
  value: string;
  neighbours: Node[];
  hasVisited: boolean;
}

type Graph = {
  nodeList: Node[];
};

function bfs(graph: Graph): void {
  const queue = new Queue();

  for (const node of graph.nodeList) {
    if (node.hasVisited) continue;

    queue.enqueue(node);

    while (!queue.isEmpty()) {
      const currentNode = queue.dequeue();
      if (currentNode.hasVisited) continue;

      currentNode.hasVisited = true;
      console.log(currentNode.value);

      currentNode.neighbours.forEach((neighbour) => {
        if (neighbour.hasVisited) return;
        queue.enqueue(neighbour);
      });
    }
  }
}

For time and space complexity, check out my post on Run Time Complexity.