"Cracking the coding interview", Graphs, 4.1

cracking-the-coding-interview-4-1.js

/**
 * Обходит граф в ширину, проверяя существует ли маршрут
 * между указанными нодами.
 * Предполагается, что граф представлен в виде списка смежности,
 * проще говоря, массива где индексами являются элементы, в значениями
 * массивы с дочерними элементами.
 * 
 * @param {Array} graph
 * @param {Number} start
 * @param {Number} end
 * @returns {Boolean}
 */
function bst(graph, start, end) {
  const visited = [];
  const queue = [start];
  
  while (queue.length > 0) {
    const node = queue.shift();
    const children = graph[node];
    
    if (children) {
      for (let i = 0; i < children.length; i++) {
        const node = children[i];
        
        if (visited[node]) {
          continue;
        }
        if (node === end) {
          return true;
        }
        visited[node] = true;
        queue.push(node);
      }
    }
  }
  return false;
}