Теория графов (Graph theory)
- Published on
- Authors
- Name
- Vasiliy Kramarenko
- @kramvas07
Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин, соединённых рёбрами
Поиск в ширину
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'));