Поиск в ширину
Поиск в ширину — это способ обхода графа, при котором сначала посещаются все вершины, находящиеся на расстоянии 1 ребро от начальной, затем на расстоянии 2, 3 и так далее. Поэтому он позволяет находить кратчайшие пути в графе без весов.
Как работает алгоритм
Сначала начальную вершину помещают в очередь и отмечают посещённой. Затем повторяют два действия: извлекают вершину из начала очереди и добавляют в её конец всех ещё не посещённых соседей. Соседей удобно получать из списка смежности. Вершина отмечается в момент добавления в очередь, чтобы не добавить её повторно.
Все вершины с одинаковым значением \(d(v)\) образуют один слой. Сначала обрабатывается слой \(0\) — начальная вершина, затем слой \(1\), слой \(2\) и так далее. Если граф не связный, поиск в ширину из одной вершины посетит только вершины её компоненты связности.
Пусть из вершины A можно попасть в B и C, из B — в D, а из C — в E. Поиск начинается с A. Очередь изменяется так: [A] → [B, C] → [C, D] → [D, E] → [E]. Слои имеют вид: 0: A; 1: B, C; 2: D, E. Значит, расстояние от A до D и E равно 2.
Поиск в ширину выбирает вершины ближайшего слоя и использует очередь. Простой путь при этом может быть восстановлен по предкам вершин. Поиск в глубину, напротив, сначала уходит как можно дальше и не гарантирует кратчайший путь в невзвешенном графе.
В каком порядке будут посещены вершины, если из A есть рёбра в B и C, а из B — в D?
Главное
- Поиск в ширину обходит граф слоями, используя очередь.
- В невзвешенном графе он находит кратчайшие пути по числу рёбер.
- Вершины отмечают при добавлении в очередь, чтобы не обрабатывать их повторно.