Как работают DFS и BFS для графа?
На этой странице
DFS и BFS обходят граф, но в графе обязательно нужен visited, иначе можно зациклиться. DFS использует стек/рекурсию, BFS использует очередь. Сложность для adjacency list обычно O(V + E).
Вопрос
Как работают DFS и BFS для графа и зачем нужен visited?
DFS
function dfs(start: string, graph: Map<string, string[]>): string[] {
const visited = new Set<string>()
const result: string[] = []
function visit(node: string): void {
if (visited.has(node)) return
visited.add(node)
result.push(node)
for (const next of graph.get(node) ?? []) {
visit(next)
}
}
visit(start)
return result
}BFS
function bfs(start: string, graph: Map<string, string[]>): string[] {
const visited = new Set([start])
const result: string[] = []
const queue = [start]
let head = 0
while (head < queue.length) {
const node = queue[head++]
result.push(node)
for (const next of graph.get(node) ?? []) {
if (!visited.has(next)) {
visited.add(next)
queue.push(next)
}
}
}
return result
}Как отличается порядок
A --- B --- D
| |
C --------- EСоседи: A: [B, C], B: [A, D], C: [A, E], D: [B, E], E: [C, D].
DFS из A: A, B, D, E, C - уходит по одной дороге до упора, потом возвращается
BFS из A: A, B, C, D, E - сначала все соседи A, потом соседи соседейБез visited DFS пошел бы A -> B -> A -> B ... бесконечно, потому что ребро A - B ведет в обе стороны.
В BFS вершину помечают visited в момент добавления в очередь, а не при извлечении. Иначе одна вершина может попасть в очередь несколько раз - например, E добавили бы и из C, и из D.
Когда DFS?
- connected components;
- cycle detection;
- topological sort;
- backtracking;
- path existence;
- flood fill.
Когда BFS?
- shortest path в unweighted graph;
- level by level;
- minimum number of steps;
- nearest target;
- word ladder-like tasks.
Что отвечать на собеседовании?
DFS идет в глубину и использует stack или recursion, BFS идет слоями и использует queue. В графах нужно множество visited, чтобы не ходить по циклам. Для adjacency list оба обхода работают за O(V + E), потому что посещают вершины и ребра.
Что важно помнить: частые ошибки
- Не использовать
visited. - Отмечать visited слишком поздно в BFS.
- Использовать
shift()для большой queue. - Путать shortest path в weighted и unweighted graph.
- Не учитывать disconnected graph.
Мини-шпаргалка
- DFS - stack/recursion.
- BFS - queue.
- Graph needs visited.
- Time
O(V + E). - BFS shortest path только для unweighted.
- Disconnected graph требует запуска из всех vertices.
Документация
Wikipedia: Breadth-first search, Wikipedia: Depth-first search.