§2. Поиск в ширину.

Другое название этого популярнейшего метода — волновой алгоритм. Причины появления такого названия станут ясны из дальнейшего.

Поиск в ширину начинается с некоторой фиксированной вер­шины v, называемой корнем. Вершину v считаем просмотренной и помещаем ее в организуемую нами очередь. Считаем также, что вершина v образует нулевой фронт распространения волны.

Затем проходим все ребра {v,w}, инцидентные v, в каком-нибудь порядке и ориентируем их из v в w. Вершины w, смежные с v, считаем просмотренными и размещаем их в порядке про­смотра ребер в очередь. Для всех таких вершин w полагаем OTEЦ [w]:=v и говорим, что w просмотрена из v. Ориентирован­ные ребра (v,w) будем называть ребрами ПВШ(v)-дерева. Гово­рят часто, что все такие вершины w образуют первый фронт рас­пространения волны. Вершина v после этих действий считается использованной и удаляется из очереди.

Дальнейший поиск продолжается следующим образом. Берем очередную вершину v из очереди, проходим по всем ребрам, ин­цидентным v, которые соединяют вершину v с еще непросмот­ренными вершинами w. Все такие вершины w объявляются про­смотренными, для них полагают OTEЦ[w]:=v, ребра (v,w) отно­сят к ПВШ(v)-дереву. После этих действий вершина v считается использованной и удаляется из очереди. Говорят также, что вер­шины, просмотренные из вершин, принадлежащих фронту с но­мером k, образуют (k+1)-ый фронт распространения волны.

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

На рисунке 4.2 показано, как поиск в ширину исследует графG, изображенный ранее на рис.4.1. Дуги ПВШ-деревьев изобра­жены стрелками в соответствии с ориентацией, полученной в хо­де поиска. Прочие ребра исходного графа изображены пункти­ром. Предполагалось, что вершины в ходе поиска просматрива­лись в порядке возрастания их номеров.

Отметим, что в ПВШ(1) - дереве поиска вершины 2, 3, 4 обра­зуют первый фронт распространения волны, вершины 5, 6 и 7 — второй, а вершина 8 — третий.

АЛГОРИТМ 4.2. ПОИСК В ШИРИНУ

Данные: неориентированный граф G=(V,E), заданный списками смежностей.

Результаты: массив ОТЕЦ, множество D.

1. procedure ПВШ(v); (* поиск в ширину с корнем v *)

2. begin ОЧЕРЕДЬ :=Ø; ОЧЕРЕДЬ v; METKA[v]:=1;

3. while ОЧЕРЕДЬ ≠Ø do

4. begin u ОЧЕРЕДЬ; ОЧЕРЕДЬ;

5. for w ЗАПИСЬ[u] do (* используем вершину u *)

6. if METKA[w]=0 then

7. begin ОЧЕРЕДЬ w; OTEЦ[w]:=u; METKA[w]:=1;

8. D=Du{(u,w)};

9. end;

10. end;

11. end;

12. begin (*главная программа*)

13. D:=Ø; for vV do METKA[v]:=0; (* инициализация *)

14. for v V do

15. if METKA[v]=0 then (*v – корень*)

16. begin OTEЦ([v]:=nil; ПВШ(v);

17. end;

18. end.

В приведенном формальном описании алгоритма поиска в ширину переменная МЕТКА имеет тот же смысл, что и ранее в алгоритме 4.1. Дуги ПВШ-деревьев хранятся в множестве D. Смысл переменной ОТЕЦ объяснен выше. Просмотренные вер­шины помещаются в ОЧЕРЕДЬ и удаляются оттуда сразу после их использования (строка 4 алгоритма). В алгоритме 4.2 связ­ность графа не предполагается. Для корневых вершин поиска и только для них выполняется равенство ОТЕЦ[v]=nil.

Точно также как и ранее теорема 4.1 доказывается

Теорема 4.2. Алгоритм 4.2 ПОИСК В ШИРИНУ имеет вычис­лительную сложность O(n+m).