Алгоритмы с нуля
Поиск в ширину (BFS)
Ты знаешь как обходить дерево: начни от корня, посети его детей, потом их детей, в некотором порядке. В прошлом уроке ты выучил DFS — поиск в глубину — что исследует насколько возможно по каждой ветви перед отходом назад. Этот урок учит BFS — поиск в ширину — другой порядок: исследуй всех соседей на расстоянии 1 перед расстоянием 2. Вместо стека, используй очередь (FIFO). В отличие от DFS что ныряет глубоко, BFS распространяется широко, посещая всех вершин на текущем “уровне” перед шагом на следующий. Это имеет значение потому что BFS имеет специальное свойство: он находит кратчайший путь (по числу рёбер) в графах без весов.
После этого урока ты можешь написать BFS итеративно используя очередь. Ты понимаешь разницу между BFS и DFS: очередь против стека, слой-за-слоем против глубины. Ты можешь трассировать BFS на конкретном графе и предсказать порядок посещения. Ты понимаешь почему множество посещённых предотвращает бесконечные циклы и как дисциплина отметки-при-добавлении работает. Ты знаешь сложность BFS O(V + E) по времени и O(V) по памяти. Ты понимаешь ключевое свойство: BFS из источника находит кратчайший путь (по числу рёбер) к каждой достижимой вершине в невзвешенном графе. Следующий урок это связные компоненты, что использует BFS (или DFS) чтобы найти все разъединённые части графа.
Что это поиск в ширину?
Поиск в ширину (BFS) это обход графа, что исследует всех вершин на расстоянии d от источника перед исследованием вершин на расстоянии d+1. Он посещает каждую вершину достижимую от начальной вершины, в порядке слой-за-слоем. Ключевая структура данных это очередь (FIFO): извлеки вершину, отметь и добавь её непосещённых соседей, повтори.
BFS против DFS: очередь против стека
Оба алгоритма посещают все достижимые вершины и имеют одну сложность O(V+E) по времени. Разница это порядок:
- DFS (из прошлого урока) использует стек (LIFO). Он идёт глубоко по одной ветви, потом отходит назад чтобы исследовать другую ветвь.
- BFS использует очередь (FIFO). Он исследует всех соседей на расстоянии 1, потом всех на расстоянии 2, и так далее.
Пример: граф с вершинами 0, 1, 2, 3 и рёбра 0→1, 0→2, 1→3, 2→3:
DFS из 0: 0, 1, 3, 2 (глубина: идёт к 1, потом 3, потом отходит назад к 0, потом 2)
BFS из 0: 0, 1, 2, 3 (слой-за-слоем: уровень 0 = {0}, уровень 1 = {1,2}, уровень 2 = {3})Алгоритм BFS: отметка-при-добавлении
Стандартная дисциплина BFS это отметить вершину посещённой когда она добавляется, не когда она извлекается. Это предотвращает одну вершину от добавления многу раз:
- Начало: отметь источник посещённым, добавь его. очередь = [источник], посещённо = {источник}.
- Пока очередь не пуста:
- Извлеки вершину v.
- Для каждого соседа u вершины v:
- Если u не посещена, отметь u посещённой и добавь u.
Это гарантирует каждая вершина входит в очередь раз и процессируется раз.
Пример графа
Один и тот же граф как урок 02 (DFS):
Список смежности:
0: [1, 2]
1: [3]
2: [3]
3: [2]
Визуально:
0 → 1
↓ ↓
2 → 3
↑ ↓
+---+Трассировка BFS на примере
Начиная от вершины 0:
Начало: очередь = [0], посещённо = {0}
Шаг 1: Извлеки 0. Соседи: 1, 2.
- 1 не посещена: отметь посещённой, добавь. посещённо = {0, 1}, очередь = [1, 2]
- 2 не посещена: отметь посещённой, добавь. посещённо = {0, 1, 2}, очередь = [1, 2]
Шаг 2: Извлеки 1. Соседи: 3.
- 3 не посещена: отметь посещённой, добавь. посещённо = {0, 1, 2, 3}, очередь = [2, 3]
Шаг 3: Извлеки 2. Соседи: 3.
- 3 уже посещена: пропусти.
Шаг 4: Извлеки 3. Соседи: 2.
- 2 уже посещена: пропусти.
Шаг 5: Очередь пуста. Готово.
Порядок посещения (по извлечению): 0, 1, 2, 3
Уровни:
- Уровень 0 (расстояние 0): {0}
- Уровень 1 (расстояние 1): {1, 2}
- Уровень 2 (расстояние 2): {3}Это мощь BFS: он естественно вычисляет кратчайший путь (по числу рёбер) к каждой вершине.
BFS против обхода дерева слой-за-слоем
В уроке 07 (Деревья), ты выучил обход слой-за-слоем — процессируй все узлы на глубине d перед глубиной d+1. Это ровно BFS на дереве. BFS это обобщение на графы: один алгоритм, но с множеством посещённых чтобы обрабатывать циклы и многочисленные пути к одной вершине.
BFS с очередью
1
function bfs(startVertex, adj) {
2
const visited = new Set();
3
const queue = [startVertex];
4
5
// Отметь начальную вершину посещённой при добавлении
6
visited.add(startVertex);
7
8
while (queue.length > 0) {
9
// Извлеки вершину
10
const vertex = queue.shift();
11
console.log(vertex); // Процессируй вершину
12
13
// Добавь всех непосещённых соседей
14
for (const neighbor of adj[vertex]) {
15
if (!visited.has(neighbor)) {
16
visited.add(neighbor); // Отметь посещённой при добавлении
17
queue.push(neighbor);
18
}
19
}
20
}
21
22
return visited;
23
}
- L1 Функция берёт начальную вершину и список смежности.
- L2 Инициализируй пустое множество посещённых.
- L3 Инициализируй очередь с начальной вершиной.
- L6 Отметь начальную вершину посещённой (при добавлении, не при извлечении).
- L8 Процессируй каждую вершину в очереди.
- L10 Извлеки вершину из начала очереди.
- L13 Для каждого соседа, проверь если он был посещён.
- L14 Отметь соседа посещённым сразу же (при добавлении).
- L15 Добавь соседа в очередь.
Ключевой момент: дисциплина отметки-при-добавлении
Отметь вершину посещённой когда ты её добавляешь, не когда ты её извлекаешь. Это гарантирует каждая вершина добавляется ровно раз. Если ты отмечаешь её посещённой только при извлечении, один сосед мог добавить её в очередь снова.
Запуск BFS на примере графа
1
adj = { 0: [1, 2], 1: [3], 2: [3], 3: [2] };
2
queue = [0];
3
visited = {0};
Сложность по времени: O(V + E)
BFS добавляет каждую вершину ровно раз (из-за дисциплины отметки-при-добавлении) и исследует каждое ребро ровно раз. Каждая вершина извлекается раз, и когда извлекается, все её соседи исследуются. Итоговая работа: V вершин добавлено + E рёбер исследовано = O(V + E).
Пример: граф с 5 вершинами и 7 рёбрами запускает BFS за O(5 + 7) = O(12) времени — независимо от того редкий ли граф или плотный.
Сложность по памяти: O(V)
Множество посещённых вершин хранит до V вершин: O(V).
Очередь может удерживать до V вершин одновременно (самое большое все вершины на текущем уровне): O(V).
Итоговая память: O(V).
В широком, мелком графе (как звезда с одной центральной вершиной соединённой со многими другими), очередь может расти большой. В глубоком, узком графе (длинная цепь), очередь остаётся маленькой.
Почему дисциплина отметки-при-добавлении
Без отметки-при-добавлении, вершина могла быть добавлена много раз:
Плохо (отметка-при-извлечении):
Вершина 1 имеет двух соседей: 2 и 3.
Вершина 2 имеет соседа 4.
Вершина 3 имеет соседа 4.
Когда извлекаешь 1:
- Добавь 2 (не отмечена ещё).
- Добавь 3 (не отмечена ещё).
Когда извлекаешь 2:
- Сосед 4 не отмечена, так добавь 4.
Когда извлекаешь 3:
- Сосед 4 не отмечена, так добавь 4 снова! (дубликат в очереди)
Хорошо (отметка-при-добавлении):
Когда процессируешь 1:
- Отметь 2 посещённой, добавь 2.
- Отметь 3 посещённой, добавь 3.
Когда процессируешь 2:
- Отметь 4 посещённой, добавь 4.
Когда процессируешь 3:
- 4 уже посещена, пропусти.
4 входит в очередь ровно раз.Какую структуру данных BFS использует чтобы процессировать вершины в порядке возрастающего расстояния от источника?
В BFS, когда ты должен отметить вершину как посещённую?
Что гарантирует BFS в невзвешенном графе?
Какая сложность по времени BFS на графе с V вершинами и E рёбрами?
Почему BFS нужно множество посещённых (или массив) чтобы избежать бесконечных циклов на циклических графах?
Граф имеет 8 вершин и 12 рёбер. Какая примерная сложность по времени O(V + E) в терминах итогового числа операций?
lesson.inset.undefined
Почему BFS вместо DFS? Оба посещают все достижимые вершины за O(V+E) времени. Используй BFS когда ты нужна кратчайший путь в невзвешенном графе, или когда ты хочешь процессировать вершины по расстоянию. Используй DFS когда ты хочешь обнаружить циклы (более естественно с рекурсией) или когда ты предпочитаешь более простой код. Для этого урока, BFS это критично для понимания кратчайших путей без весов.
lesson.inset.undefined
Отметка посещённой слишком поздно. Забывание отметить соседей посещёнными когда добавляешь их может вести к одной вершине добавляясь много раз. Каждый раз когда другой сосед открывает уже-добавленную вершину, она добавляется снова. Это тратит место в очереди и время. Всегда отметка-при-добавлении.
lesson.inset.undefined
Несвязные графы. Если граф имеет многочисленные несвязные компоненты, BFS из одной вершины посетит только вершины достижимые из этой вершины. Чтобы посетить все вершины в несвязном графе, ты должен начать новый BFS из непосещённой вершины. Это как алгоритм связных-компонент работает (идущего в следующем уроке).
lesson.inset.undefined
BFS для кратчайших путей. BFS отвечает вопрос: “Какой кратчайший путь (по числу рёбер) из источника A к каждой другой достижимой вершине?” Запусти BFS, и отслеживай расстояние к каждой вершине (расстояние растёт на 1 каждый раз когда ты движешься к соседу на следующем уровне). Это основание для более продвинутых алгоритмов кратчайших путей как Dijkstra (урок 09/06).
Объясни что такое BFS, как он отличается от DFS, почему множество посещённых и дисциплина отметки-при-добавлении критичны, и опиши BFS ключевое свойство в невзвешенных графах.
Поиск в ширину (BFS) исследует граф слой за слоем, процессируя все вершины на расстоянии d перед расстоянием d+1. Он использует очередь (FIFO), не стек, и множество посещённых чтобы предотвратить бесконечные циклы и дубликаты при добавлении.
Дисциплина отметки-при-добавлении: Отметь вершину посещённой когда ты её добавляешь, гарантируя каждая вершина добавляется ровно раз.
Время: O(V + E). Память: O(V).
Ключевое свойство: В невзвешенном графе, BFS из источника находит кратчайший путь (по числу рёбер) к каждой достижимой вершине — первый раз ты достигаешь вершину это через кратчайший маршрут.
BFS распространяется широко. DFS идёт глубоко. Следующий урок: связные компоненты — используй BFS или DFS чтобы найти все разъединённые части графа.