7_breadthFirstSearch.js

// Поиск в ширину в графе (Breadth First Search)

// Граф - это некая абстрактная структура данных, предствляющая собой множество
// вершин и набор ребер(т.е соединений между парами вершин).
// Ребра бывают однонаправленными и двунаправленными, то есть если из "A" можно попасть только в "B" - это однонаправленность.
// А если можно из "A" в "B" и из "B" в "A" - - это двунаправленность.

const graph = {};
graph.a = ["b", "c"];
graph.b = ["f"];
graph.c = ["d", "e"];
graph.d = ["f"];
graph.e = ["f"];
graph.f = ["g"];

// Задача: Найти существует ли путь из точки "A" в точку "G" за минималльное кол-во шагов.

// Этот алгоритм:
// 1) Решает задачу поиска пути в графу, существует ли такой путь
// 2) Находит путь за минимальное кол-во шагов
function breadthSearch(graph, start, end) {
  // Очередь(queue) - структура данных состоящая из каких-то элементов.
  // Основной принцип заключается в том, что элементы всегда добавляются в конец структуры, а
  // извлекаются из ее начала. Принцип как в очереди в жизни: кто первым пришел на кассу, тот из
  // нее первый и уходит. Такой принцип называется FIFO - first in first out.
  let queue = [];
  //   В очередь сразу добавляем стартовую вершину(start, в данном случае "a")
  queue.push(start);
  //   Крутим цикл while пока в очереди есть хотя бы один элемент
  while (queue.length > 0) {
    // Из начала очереди достаем текущую вершину
    const current = queue.shift();
    // Если по текущей вершине в графе ничего не находится, то присваиваем этой вершине пустой массив
    if (!graph[current]) {
      graph[current] = [];
    }
    // Если в графе по текущей вершине массив содержит конечную точку, то мы завершаем выполнение
    // программы и возвращаем true. То есть на данном этапе мы обошли весь граф и пришли
    // к пункту назначения.
    if (graph[current].includes(end)) {
      return true;
    } else {
      // Если это условие не отработало, то мы должны добавить в очередь новые вершины.
      //   Поэтому разворачиваем то, что уже находится в очереди в массив и в конец разворачиваем массив
      //   который лежит в графе по текущей вершине.
      queue = [...queue, ...graph[current]];
    }
  }
  return false;
}

console.log(breadthSearch(graph, "a", "e"));