Function bfsShortestPath

src/13-graph/bfs.js:41–75

(graph, startVertex)

};

const bfsShortestPath = (graph, startVertex) => {
  const vertices = graph.vertices;
  const adjList = graph.adjList;
  const color = {};
  const dist = {};
  const pred = {};
  const queue = [startVertex];

  vertices.forEach(vertex => {
    color[vertex] = Colors.WHITE;
    dist[vertex] = 0;
    pred[vertex] = null;
  });

  while (queue.length) {
    const visiting = queue.shift();
    const neighbors = adjList.get(visiting);
    color[visiting] = Colors.GREY;
    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i];
      if (color[neighbor] === Colors.WHITE) {
        color[neighbor] = Colors.GREY;
        dist[neighbor] = dist[visiting] + 1;
        pred[neighbor] = visiting;
        queue.push(neighbor);
      }
    }
    color[visiting] = Colors.BLACK;
  }

  return {
    distances: dist,
    predecessors: pred
  };
};

module.exports = { breadthFirstSearch , bfsShortestPath };