Графы: BFS и DFS
↑ 8.3 Алгоритмы и структуры данных · ← Предыдущая · → Следующая
Зачем это на собесе
Графы встречаются в зависимостях модулей, маршрутах, задачах на «острова»; знать нужно представление и два обхода.
Представление
// список смежности
const graph = new Map<string, string[]>([
['A', ['B', 'C']], ['B', ['D']], ['C', ['D']], ['D', []],
])| Представление | Память | Проверка ребра | Обход соседей |
|---|---|---|---|
| Список смежности | O(V + E) | O(deg) | O(deg) |
| Матрица смежности | O(V²) | O(1) | O(V) |
BFS (в ширину)
function bfs(g: Map<string, string[]>, start: string) {
const seen = new Set([start]), q = [start], order: string[] = []
while (q.length) {
const v = q.shift()!; order.push(v)
for (const n of g.get(v) ?? []) if (!seen.has(n)) { seen.add(n); q.push(n) }
}
return order
}Кратчайший путь в невзвешенном графе; уровни.
DFS (в глубину)
function dfs(g: Map<string, string[]>, v: string, seen = new Set<string>()) {
seen.add(v)
for (const n of g.get(v) ?? []) if (!seen.has(n)) dfs(g, n, seen)
return seen
}Поиск компонент связности, обнаружение циклов, топологическая сортировка.
Типовые задачи
// число островов на сетке
function islands(grid: string[][]) {
let count = 0
const dfs = (r: number, c: number) => {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] !== '1') return
grid[r][c] = '0'
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
}
for (let r = 0; r < grid.length; r++) for (let c = 0; c < grid[0].length; c++) if (grid[r][c] === '1') { count++; dfs(r, c) }
return count
}- Топологическая сортировка: порядок сборки модулей, зависимостей задач (Kahn с входящими степенями);
- Цикл в направленном графе: DFS с состояниями white/gray/black;
- Дейкстра: кратчайший путь во взвешенном графе с неотрицательными весами (heap), O((V+E) log V);
- Union-Find: компоненты связности.
Во фронтенде
Граф зависимостей бандлера, граф реактивности, маршруты, соцсети, дерево компонентов.
Вопросы с ответами
Когда BFS, когда DFS?
BFS — кратчайший путь по числу рёбер, обход по уровням. DFS — обход в глубину, циклы, компоненты, топологическая сортировка, перебор с возвратом.
Как обнаружить циклическую зависимость модулей?
DFS с отметками состояний (в процессе / завершено); встреча узла «в процессе» означает цикл. Либо топологическая сортировка: если обработаны не все узлы, цикл есть.