Breadth-First Search

Breadth-First Search is an algorithm for searching graph data structures. It starts at a specified source node and explores all its immediate neighbors before moving on to the next level of neighbors.

/**
 * @file Breadth-First Search
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Represents the possible states that can be assigned to vertices while
 * traversing the graph.
 */
enum Color {
  /** Vertex has not been visited. */
  White = 0,
  /** Vertex is being visited */
  Gray = 1,
  /** Vertex has been fully visited */
  Black = 2,
}

/** Represents a node in a Directed Acyclic Graph (DAG). */
class Vertex<T> {
  /** An array of vertices connected to this vertex. */
  adjacent: Array<Vertex<T>> = [];
  /** The parent vertex in a traversal of the graph. */
  parent?: Vertex<T> = undefined;
  /** Steps away from the starting vertex in a graph traversal. */
  distance = Infinity;
  /** State of the vertex in a traversal. */
  color: Color = Color.White;

/** @param value The value of the vertex. */
  constructor(public value: T) {}
}

/**
 * Performs a breadth-first search (BFS) on a graph starting from a given
 * vertex. Initializes all vertices as unvisited and then processes them level
 * by level.
 *
 * @param graph An array of all vertices in the graph.
 * @param search The starting vertex for the BFS.
 */
function bfs<T>(graph: Array<Vertex<T>>, search: Vertex<T>) {
  for (const vertex of graph) {
    vertex.color = Color.White;
    vertex.distance = Infinity;
    vertex.parent = undefined;
  }

search.color = Color.Gray;
  search.distance = 0;
  search.parent = undefined;

const queue = [search];

while (queue.length > 0) {
    const vertex: Vertex<T> | undefined = queue.shift();
    if (!vertex) {
      break;
    }

for (const adjacentVertex of vertex.adjacent ?? []) {
      if (adjacentVertex.color === Color.White) {
        adjacentVertex.color = Color.Gray;
        adjacentVertex.distance = vertex.distance + 1;
        adjacentVertex.parent = vertex;

queue.push(adjacentVertex);
      }
    }

vertex.color = Color.Black;
  }
}

/**
 * Prints the path from the search start vertex to a specific vertex
 * recursively. If no path exists, it outputs an appropriate message.
 *
 * @param graph The graph containing all vertices.
 * @param search The starting vertex of the search.
 * @param vertex The target vertex to which the path is to be printed.
 */
function printPath<T>(
  search: Vertex<T>,
  vertex: Vertex<T>,
): string | undefined {
  const path: Array<string | undefined> = [];

function trace<T>(search: Vertex<T>, vertex: Vertex<T>) {
    if (vertex === search) {
      path.push(String(search.value));
    } else if (vertex.parent === undefined) {
      path.push(
        `No path from ${String(search.value)} to ${String(vertex.value)} exists.`,
      );
    } else {
      trace(search, vertex.parent);
      path.push(String(vertex.value));
    }
  }

trace(search, vertex);
  return path.join(' -> ');
}

// Usage
(() => {
  // Create a cyclic Graph
  const vertexA = new Vertex<string>('A');
  const vertexB = new Vertex<string>('B');
  const vertexC = new Vertex<string>('C');

vertexA.adjacent.push(vertexB);
  vertexB.adjacent.push(vertexC);
  vertexC.adjacent.push(vertexA); // Creating a cycle

bfs([vertexA, vertexB, vertexC], vertexA);

if (vertexA.color !== Color.Black) {
    throw new Error('Vertex A should be fully visited in a cycle');
  }

if (vertexB.color !== Color.Black) {
    throw new Error('Vertex B should be fully visited in a cycle');
  }

if (vertexC.color !== Color.Black) {
    throw new Error('Vertex C should be fully visited in a cycle');
  }

if (vertexC.distance !== 2) {
    throw new Error(
      `Distance of C from A should be 2, got ${vertexA.distance}`,
    );
  }

const result = printPath(vertexA, vertexC);

if (result !== 'A -> B -> C') {
    throw new Error(
      `Should print path A -> B -> C in cyclic graph, got '${result}'`,
    );
  }
})();