MV's blog

Breadth First Search

Breadth first search is an algorithm for processing all the verteces connected to a given vertex in a graph. It uses a queue as an auxilary data structure. It starts with the given vertex and adds it to the queue, it then marks that vertex as visited and adds it's neightbours to the queue. The algorithm then dequeues a vertex from the queue and repeats the procedure -- marks it as visited and adds all it's neighbours to the queue. It does this until there are no more verteces in the queue. Because the queue is a FIFO data structure it follows that the algorithm will process the connected nodes in increasing distance from the given vertex i.e it will first process all the nodes that are at a distance 1 then at a distance 2 and so on.. From this follows that the path from the given node to any other visited node is also the shortest path.

Sample typescript implementation

export class BFS {
  private g: Graph;
  private s: number;

  private visited: boolean[];
  private path: number[];

  constructor(g: Graph, s: number) {
    this.g = g;
    this.s = s;

    this.visited = [];
    this.path = [];

    this.bfs(s);
  }

  public hasPathTo(v: number): boolean {
    return this.visited[v] ?? false;
  }

  public pathTo(v: number): number[] {
    if (!this.hasPathTo(v)) return [];

    const path: number[] = [];
    for (let p = v; p != this.s; p = this.path[p]) {
      path.push(p);
    }

    return path;
  }

  private bfs(v: number): void {
    const q: Queue<number> = new Queue<number>();

    this.visited[v] = true;
    q.enqueue(v);

    while (!q.isEmpty()) {
      const p = q.dequeue();
      for (let n of this.g.adj(p)) {
        if (!this.visited[n]) {
          this.visited[n] = true;
          q.enqueue(n);
        }
      }
    }
  }
}