Обход в ширину

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

Он полностью аналогичен волновому алгоритму, и отличается от него лишь тем, что, когда мы нашли расстояние до некотрой вершины, мы помещаем эту вершину в очередь. А когда мы ищем вершину, чтобы "ходить" из нее (и попытаться в ее соседей поставить числа на один большее), в волновом алгоритме мы просматривали все вершины и искали те, в которых стоит число k-1, в обходе в ширину мы просто извлекаем из очереди очередную вершину и "ходим из нее".

Таким образом, в псевдокоде обход в ширину можно записать так:

a[i,j] - матрица смежности
b[i] - расстояние до вершины i (если оно еще не известно, то -1)

Заполняем b значением -1
b[начальная вершина]:=0
заносим в очередь номер начальной вершины
ПОКА очередь не пуста, делаем следующее:
   извлекаем ВЕРШИНУ из очереди
   просматриваем всех ее СОСЕДЕЙ, 
      если расстояние до СОСЕДА еще не известно, то
         расстояние до СОСЕДА:=расстояние до ВЕРШИНЫ + 1 и помещаем СОСЕДА в очередь

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