Part 2 in the series Graph Algorithms, Implementing Breadth First Search (BFS) in Typescript. For a primer on BFS and it's applications and procedure, read Part 1: Graph Algorithms: Breadth First Search (BFS) here.

Data Structures

For convenience and clarity of code, the following types were implmenented for use in BFS

// data structure that represents an edge,
// this really does nothing for the algorithm directly but provides type safety.
export type Edge = [src: number, dest: number];

export class Graph {
  // array of arrays to represent adjacency list
  private adjList: number[][];
  constructor(edges: Edge[], N: number) {
    //initialize the adjacency list with the size of the graph (number of nodes)
    this.adjList = Array.from({ length: N }, () => []);

    for (const [src, dest] of edges) {
      this.adjList[src].push(dest);
      this.adjList[dest].push(src);
    }
  }

  public getAdjacent(index: number): number[] | null {
    return this.adjList[index] ? this.adjList[index] : null;
  }
}
// this is not truly necessary to do for the algorith,
// moreso a nicety becuase there is no such thing as a queue in javascript,
// only arrays.
// This class encapsulates FIFO behavior to clean up the BFS implementation
export class Queue<T> {
  private stack: T[] = [];
  public push(element: T): void {
    this.stack.push(element);
  }
  public pop(): T | null {
    const el = this.stack.shift();

    return el ?? null;
  }

  public empty(): boolean {
    return this.stack.length === 0;
  }
}

Iterative Implementation of BFS

export const iterativeBFS = (
  graph: Graph,
  v: number,
  discovered: boolean[]
): void => {
  //create the queue
  const q = new Queue<number>();
  // mark the root as having been discovered
  discovered[v] = true;

  // push the starting index into the queue
  q.push(v);

  while (q.empty() !== true) {
    // while the queue isn't empty, take from it
    v = q.pop()!;

    //print the node to the console
    console.log("node:", v);

    // get the adjacent nodes to v
    const adjacent = graph.getAdjacent(v);
    if (adjacent) {
      adjacent.forEach((u) => {
        if (!discovered[u]) {
          discovered[u] = true;
          q.push(u);
        }
      });
    }
  }
};

Output

const edges: Edge[] = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 5],
  [2, 6],
  [5, 9],
  [5, 10],
  [4, 7],
  [4, 8],
  [7, 11],
  [7, 12],
];
// vertex 0, 13, and 14 are single nodes
const N = 15;

(() => {
  let graph = new Graph(edges, N);
  let discovered = Array.from({ length: N }, () => false);
  Array.from({ length: N }, (_, idx) => {
    if (!discovered[idx]) {
      iterativeBFS(graph, idx, discovered);
    }
  });
})();

$ npx tsc && node dist
node: 0
node: 1
node: 2
node: 3
node: 4
node: 5
node: 6
node: 7
node: 8
node: 9
node: 10
node: 11
node: 12
node: 13
node: 14

Recursive Implementation of BFS

export const recursiveBFS = (
  graph: Graph,
  queue: Queue<number>,
  discovered: boolean[]
) => {
  // if our queue is empty, bail
  if (queue.empty()) {
    return;
  }
  // retrieve the node off of the top of the queue
  const v = queue.pop()!;

  // print the node to the console
  console.log("node:", v);

  // get the adjacent nodes to the current index
  const adjacent = graph.getAdjacent(v);

  // if there are adjacent nodes...
  if (adjacent) {
    // filter down to the nodes that have not yet been discovered
    adjacent
      .filter((u) => !discovered[u])
      .forEach((u) => {
        // for each undiscovered node, mark it "visited"/discovered
        discovered[u] = true;
        //push the discovered node onto the queue for it's edges to be traced
        queue.push(u);
      });
  }
  recursiveBFS(graph, queue, discovered);
};

output

const edges: Edge[] = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 5],
  [2, 6],
  [5, 9],
  [5, 10],
  [4, 7],
  [4, 8],
  [7, 11],
  [7, 12],
];
// vertex 0, 13, and 14 are single nodes
const N = 15;

(() => {
  // create the graph from edges
  let graph = new Graph(edges, N);

  // create an array to track discovered nodes
  let recursiveDiscovered = Array.from({ length: N }, () => false);

  //queue of nodes that need neighbor discovery
  let recursiveQueue = new Queue<number>();
  Array.from({ length: N }, (_, idx) => {
    // for each of our nodes, we're not yet discovered, call the recursive bfs
    if (!recursiveDiscovered[idx]) {
      recursiveDiscovered[idx] = true;
      recursiveQueue.push(idx);
      recursiveBFS(graph, recursiveQueue, recursiveDiscovered);
    }
  });
})();

recursive approach:
node: 0
node: 1
node: 2
node: 3
node: 4
node: 5
node: 6
node: 7
node: 8
node: 9
node: 10
node: 11
node: 12
node: 13
node: 14