Поиск в ширину (BFS)
Обходит граф слой за слоем. Какую вершину брать дальше, решает очередь, поэтому ближайшие вершины всегда посещаются первыми.
- время O(V + E)
- память O(V)
- использует очередь
Что это значит?
- Вершина: точка графа, здесь нарисована кружком с буквой.
- Ребро: линия, соединяющая две вершины. Здесь по нему можно пройти в обе стороны.
- Соседи: вершины, соединённые с данной вершиной ребром. Их просматривают в алфавитном порядке.
- Очередь: первым пришёл, первым ушёл. BFS всегда берёт вершину, которая ждёт дольше всех.
- Стек: последним пришёл, первым ушёл. DFS всегда продолжает с вершины, до которой добрался последней.
- V и E: число вершин и рёбер. O(V + E) значит, что каждая вершина и каждое ребро обрабатываются фиксированное число раз.
- в очереди
- текущая
- готова
- ребро дерева поиска
- пропущенное ребро
Начинаем с вершины A. Нажмите «Воспроизвести» или проходите поиск по шагам.
Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.
Попробуйте: Выберите граф из двух частей. До вершин, не связанных со стартом, поиск так и не дойдёт.
Как это работает
BFS ставит стартовую вершину в очередь. Затем раз за разом берёт вершину из начала очереди и добавляет её новых соседей в конец. Очередь обслуживает в порядке поступления, поэтому каждая вершина на расстоянии одного ребра готова раньше любой вершины на расстоянии двух. Число рядом с вершиной означает её расстояние от старта: наименьшее число рёбер, по которым до неё можно дойти.
Когда стоит применять
BFS нужен, когда надо найти кратчайший путь в шагах: меньше всего ходов в головоломке, меньше всего переходов в сети, друзей и друзей друзей. На большом графе очередь может сильно вырасти, потому что держит целый слой сразу.