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