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