В каких реальных задачах применяется алгоритм поиска в ширину?

Некоторые реальные задачи, в которых применяется алгоритм поиска в ширину:

• Поиск кратчайшего пути в неявно заданных графах. ru.algorithmica.org Например, если дана булева матрица, в которой помечено, свободна ли клетка с координатами (x, y), и требуется найти кратчайший путь от (xs, yt) до (xy, yt) при условии, что за один шаг можно перемещаться в свободную соседнюю по вертикали или горизонтали клетку. ru.algorithmica.org
• Моделирование явлений, в которых источник «волны» не один. ru.algorithmica.org Например, пожар, наводнение, извержение вулкана. ru.algorithmica.org В этом случае в очередь изначально добавляют не одну, а несколько вершин, и находят для каждой вершины кратчайшее расстояние до одной из них. ru.algorithmica.org
• Решение игр. ru.algorithmica.org www.e-maxx-ru.1gb.ru Например, когда нужно собрать кубик Рубика за наименьшее число ходов. ru.algorithmica.org В этом случае каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа. ru.algorithmica.org
• Нахождение кратчайшего цикла в ориентированном невзвешенном графе. ru.algorithmica.org www.e-maxx-ru.1gb.ru Для этого производят поиск в ширину из каждой вершины и среди всех найденных циклов выбирают кратчайший. www.e-maxx-ru.1gb.ru