Теория графов (Graph theory)

Published on
Authors

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин, соединённых рёбрами

Поиск в ширину

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

function breadthSearch(graph, start, end) {
  let queue = [];
  queue.push(start);

  while (queue.length > 0) {
    const current = queue.shift();
    
    if (!graph[current]) {
      graph[current] = [];
    }

    if (graph[current].includes(end)) {
      return true;
    } else {
      queue = [...queue, ...graph[current]];
    }
  }
  return false;
}

console.log(breadthSearch(graph, 'a', 'c'));
console.log(breadthSearch(graph, 'a', 'n'));