Поиск кратчайшего пути в невзвешенном графе

Поиск компонент связности в графе за .

Для этого мы просто запускаем обход в ширину от каждой вершины, за исключением вершин, оставшихся посещёнными () после предыдущих запусков. Таким образом, мы выполняем обычный запуск в ширину от каждой вершины, но не обнуляем каждый раз массив , за счёт чего мы каждый раз будем обходить новую компоненту связности, а суммарное время работы алгоритма составит по-прежнему (такие несколько запусков обхода на графе без обнуления массива называются серией обходов в ширину).

Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа.

Классический пример — игра, где робот двигается по полю, при этом он может передвигать ящики, находящиеся на этом же поле, и требуется за наименьшее число ходов передвинуть ящики в требуемые позиции. Решается это обходом в ширину по графу, где состоянием (вершиной) является набор координат: координаты робота, и координаты всех коробок.

Нахождение кратчайшего пути в 0-1-графе ( т.е. графе взвешенном, но с весами равными только 0 либо 1): достаточно немного модифицировать поиск в ширину: если текущее ребро нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди.

Нахождение кратчайшего цикла в ориентированном невзвешенном графе:

производим поиск в ширину из каждой вершины; как только в процессе обхода мы пытаемся пойти из текущей вершины по какому-то ребру в уже посещённую вершину, то это означает, что мы нашли кратчайший цикл, и останавливаем обход в ширину; среди всех таких найденных циклов (по одному от каждого запуска обхода) выбираем кратчайший.

Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин . Для этого надо запустить 2 поиска в ширину: из , и из . Обозначим через массив кратчайших расстояний, полученный в результате первого обхода, а через — в результате второго обхода. Теперь для любого ребра легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет условие .

Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин . Для этого надо запустить 2 поиска в ширину: из , и из . Обозначим через массив кратчайших расстояний, полученный в результате первого обхода, а через — в результате второго обхода. Теперь для любой вершины легко проверить, лежит ли он на каком-либо кратчайшем пути: критерием будет условие .

Найти кратчайший чётный путь в графе (т.е. путь чётной длины). Для этого надо построить вспомогательный граф, вершинами которого будут состояния , где — номер текущей вершины, — текущая чётность. Любое ребро исходного графа в этом новом графе превратится в два ребра и . После этого на этом графе надо обходом в ширину найти кратчайший путь из стартовой вершины в конечную, с чётностью, равной 0.