Обход графа в ширину (BFS)
Идём от стартовой вершины «волнами», сначала посещая всех соседей, потом их соседей и так далее.
Идея алгоритма
BFS использует очередь. Сначала в очередь кладётся стартовая вершина. Потом мы берём вершину из начала очереди, посещаем её и добавляем в очередь ещё не посещённых соседей. Так мы обходим граф слоями.
Сложность:
- Время: O(V + E)
- Память: O(V)
- V — вершины, E — рёбра.
Плюсы
- Находит кратчайший путь по количеству рёбер в невзвешенном графе;
- Работает на любых структурах графа (списки, матрицы смежности);
- Простая идея, легко реализовать.
Минусы
- Может потребовать много памяти при широких графах;
- Не учитывает веса рёбер.
Пример кода
function bfs(adj, start) {
const visited = new Set();
const queue = [start];
visited.add(start);
while (queue.length) {
const v = queue.shift();
console.log(v);
for (const to of adj[v] ?? []) {
if (!visited.has(to)) {
visited.add(to);
queue.push(to);
}
}
}
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания