Поиск в ширину (BFS)
Последнее обновление
Поиск в ширину исследует граф уровень за уровнем. Начиная с исходного узла, он сначала посещает всех его непосредственных соседей, затем всех непосещённых соседей этих узлов и так далее - расширяясь наружу кольцами возрастающего расстояния. Нажмите воспроизведение выше, чтобы увидеть, как он расходится от начального узла слой за слоем.
BFS использует очередь типа «первым пришёл - первым вышел», что и задаёт порядок уровень за уровнем. Поскольку он достигает узлов в порядке расстояния в переходах, BFS находит кратчайший путь (наименьшее число рёбер) в невзвешенном графе. Он посещает каждый узел и ребро один раз, поэтому работает за время O(V + E).
Временная и пространственная сложность
| Показатель | Сложность | Примечания |
|---|---|---|
| Время | O(V + E) | Каждая вершина и ребро посещаются один раз |
| Память | O(V) | Очередь + множество посещённых, в худшем случае все узлы |
| Обход | Уровень за уровнем | Ближайшие узлы первыми, кольцами |
| Кратчайший путь | Да (невзвешенный) | Достигает каждого узла по наименьшему числу рёбер |
Шаг за шагом
| Шаг | Что происходит |
|---|---|
| 1 | Поместите исходный узел в очередь. |
| 2 | Извлеките передний узел и отметьте его как посещённый. |
| 3 | Рассмотрите каждого из его соседей. |
| 4 | Поместите в очередь любого соседа, который ещё не посещён и не в очереди. |
| 5 | Повторяйте, пока очередь не опустеет. |
Разобранный пример
Обход этого графа от узла 0, где 0-1, 0-2, 1-3, 2-3, 2-4 - рёбра:
| Шаг | Посещённые | Очередь (граница) |
|---|---|---|
| Начало | {} | [0] |
Извлечь 0 | {0} | [1, 2] |
Извлечь 1 | {0, 1} | [2, 3] |
Извлечь 2 | {0, 1, 2} | [3, 4] |
Извлечь 3 | {0, 1, 2, 3} | [4] |
Извлечь 4 | {0, 1, 2, 3, 4} | [] (готово) |
Когда использовать BFS
| Используйте, когда | Избегайте, когда |
|---|---|
| Вам нужен кратчайший путь в невзвешенном графе | У рёбер есть веса - используйте вместо этого Dijkstra |
| Цель, вероятно, находится близко к источнику | Граф очень широкий - очередь может хранить огромную границу |
| Вы хотите исследовать граф в порядке уровней | Вам нужно лишь достичь любого узла, где DFS использует меньше памяти |
| Вы ищете компоненты связности или маршрут с минимумом переходов | Вам нужна топологическая сортировка или обнаружение циклов - DFS подходит лучше |
Код Breadth-First Search
Чистая, готовая к запуску реализация Breadth-First Search на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Breadth-First Search на Python
Python
1from collections import deque2
3
4def bfs(graph, start):5 visited = {start}6 queue = deque([start])7 order = []8 while queue:9 node = queue.popleft()10 order.append(node)11 for neighbor in graph[node]:12 if neighbor not in visited:13 visited.add(neighbor) # mark on enqueue, not dequeue14 queue.append(neighbor)15 return order16
17
18graph = {19 "A": ["B", "C"],20 "B": ["D", "E"],21 "C": ["F"],22 "D": [],23 "E": ["F"],24 "F": [],25}26
27print("BFS order:", " -> ".join(bfs(graph, "A")))Код Breadth-First Search на JavaScript
JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function bfs(start) {11 const visited = new Set([start]);12 const queue = [start];13 const order = [];14 while (queue.length > 0) {15 const node = queue.shift(); // Dequeue the oldest node16 order.push(node);17 for (const next of graph[node]) {18 if (!visited.has(next)) {19 visited.add(next);20 queue.push(next);21 }22 }23 }24 return order;25}26
27console.log("BFS from A:", bfs("A").join(" -> "));Код Breadth-First Search на Java
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 List<List<Integer>> adj = List.of(8 List.of(1, 2), // neighbors of 09 List.of(0, 3, 4), // neighbors of 110 List.of(0, 5),11 List.of(1),12 List.of(1, 5),13 List.of(2, 4)14 );15 boolean[] visited = new boolean[adj.size()];16 Queue<Integer> queue = new ArrayDeque<>();17 visited[0] = true;18 queue.add(0);19
20 StringBuilder order = new StringBuilder("BFS from 0:");21 while (!queue.isEmpty()) {22 int node = queue.poll();23 order.append(" ").append(node);24 // Mark neighbors when enqueued so nothing enters twice25 for (int next : adj.get(node)) {26 if (!visited[next]) {27 visited[next] = true;28 queue.add(next);29 }30 }31 }32 System.out.println(order);33 }34}Код Breadth-First Search на C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5void bfs(int start, const std::vector<std::vector<int>>& adj) {6 std::vector<bool> visited(adj.size(), false);7 std::queue<int> frontier;8 visited[start] = true;9 frontier.push(start);10 // Visit nodes level by level11 while (!frontier.empty()) {12 int node = frontier.front();13 frontier.pop();14 std::cout << node << " ";15 for (int next : adj[node]) {16 if (!visited[next]) {17 visited[next] = true;18 frontier.push(next);19 }20 }21 }22}23
24int main() {25 // 6-node undirected graph as an adjacency list26 std::vector<std::vector<int>> adj = {27 {1, 2}, // 028 {0, 3, 4}, // 129 {0, 5}, // 230 {1}, // 331 {1, 5}, // 432 {2, 4}, // 533 };34 std::cout << "BFS from node 0: ";35 bfs(0, adj);36 std::cout << "\n";37 return 0;38}Код Breadth-First Search на C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6void bfs(int start, const int adj[N][N]) {7 bool visited[N] = {false};8 int queue[N]; // fixed-size queue: head chases tail9 int head = 0, tail = 0;10 visited[start] = true;11 queue[tail++] = start;12 // Visit nodes level by level13 while (head < tail) {14 int node = queue[head++];15 printf("%d ", node);16 for (int next = 0; next < N; next++) {17 if (adj[node][next] && !visited[next]) {18 visited[next] = true;19 queue[tail++] = next;20 }21 }22 }23}24
25int main(void) {26 // 6-node undirected graph as an adjacency matrix27 int adj[N][N] = {28 {0, 1, 1, 0, 0, 0},29 {1, 0, 0, 1, 1, 0},30 {1, 0, 0, 0, 0, 1},31 {0, 1, 0, 0, 0, 0},32 {0, 1, 0, 0, 0, 1},33 {0, 0, 1, 0, 1, 0},34 };35 printf("BFS from node 0: ");36 bfs(0, adj);37 printf("\n");38 return 0;39}Часто задаваемые вопросы о поиске в ширину
Какова временная сложность BFS?
BFS работает за время
O(V + E), где V - число вершин, а E - число рёбер, поскольку он посещает каждую вершину один раз и рассматривает каждое ребро один раз. Он использует O(V) памяти для очереди и множества посещённых.Находит ли BFS кратчайший путь?
Да, в невзвешенном графе. Поскольку BFS достигает узлов в порядке расстояния в переходах от источника, первый раз, когда он достигает узла, происходит по пути с наименьшим числом рёбер. Для взвешенных графов вам нужен алгоритм Dijkstra.
В чём разница между BFS и DFS?
BFS использует очередь и исследует уровень за уровнем (ближайшие первыми), тогда как DFS использует стек и уходит вглубь по одной ветви перед возвратом. BFS находит кратчайшие невзвешенные пути; DFS использует меньше памяти на широких графах и подходит для обнаружения циклов и топологической сортировки.
Когда следует использовать BFS вместо алгоритма Dijkstra?
Используйте BFS, когда все рёбра имеют одинаковую стоимость, так как он находит путь с наименьшим числом рёбер за время
O(V + E) без очереди с приоритетом. Алгоритм Dijkstra нужен, когда рёбра имеют разные веса; запуск чистого BFS на взвешенном графе даёт путь с наименьшим числом переходов, а не с наименьшей стоимостью.Зачем BFS нужно множество посещённых?
Графы могут содержать циклы, поэтому без множества посещённых BFS помещал бы один и тот же узел в очередь снова и снова и зациклился бы навсегда. Отметка узла при первом помещении в очередь (а не при извлечении) также не даёт одному и тому же узлу быть добавленным в очередь дважды разными соседями.
Отмечать узел как посещённый при помещении в очередь или при извлечении?
Отмечайте его при помещении в очередь. Если ждать извлечения, узел может быть добавлен в очередь несколько раз разными соседями до его обработки, тратя память и время. Отметка при помещении гарантирует, что каждый узел попадает в очередь ровно один раз.
Связанные ресурсы
Больше визуализаций
