Поиск в ширину (волновой алгоритм)

 

Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На i-ом шаге будут помечены все вершины, достижимые за i ходов, если ходом считать переход из одной вершины в другую.

 

 

procedure WidthSearch(v: integer);

var

Delayed: array[1..n] of integer; {Очередь}

Count, {Хвост очереди}

Head: integer; {Голова очереди}

Current, j: integer;

begin

Count := 1; Head := 0; Delayed[Count] := v;

Visited[v] := true;

repeat

Head := Head +1; Current := Delayed[Head];

for каждой вершины y, смежной с Current do

if not Visited[y] then begin

Count := Count + 1;

Delayed[Count] := Graph[y];

Visited[y] := true;

end;

until Count = Head;

end;

begin

while есть непомеченные вершины do begin

v := любая непомеченная вершина;

WidthSearch(v);

end;

end.

 

 

Листинг 5.1 – Поиск в ширину

 

Листинг 5.2 – Поиск в ширину

 

Данный алгоритм может быть описан и так. Пусть задан граф G = (V, Е) и фиксирована начальная вершина(source
vertex) s. Алгоритм поиска в ширину перечисляет все достижимые из s (если
идти по рёбрам) вершины в порядке возрастания расстояния от s. Расстоя-
нием считается длина (число рёбер) кратчайшего пути. В процессе поиска из
графа выделяется часть, называемая «деревом поиска в ширину» с корнем s.
Она содержит все достижимые из s вершины (и только их). Для каждой из
них путь из корня в дереве поиска будет одним из кратчайших путей (из
начальной вершины) в графе. Алгоритм применим и к ориентированным, и к
неориентированным графам.

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

Для наглядности мы будем считать, что в процессе работы алгоритма вер-
шины графа могут быть белыми, серыми и чёрными. Вначале они все белые, но в ходе работы алгоритма белая вершина может стать серой, а серая – чёрной
(но не наоборот). Повстречав новую вершину, алгоритм поиска красит её, так
что окрашенные (серые или чёрные) вершины – это в точности те, которые
уже обнаружены. Различие между серыми и чёрными вершинами используется
алгоритмом для управления порядком обхода: серые вершины образуют «линию
фронта», а чёрные – «тыл». Более точно, поддерживается такое свойство: если
(и, v) Е и и чёрная, то v – серая или чёрная вершина. Таким образом, только
серые вершины могут иметь смежные необнаруженные вершины.

Вначале дерево поиска состоит только из корня – начальной вершины s.
Как только алгоритм обнаруживает новую белую вершину v, смежную с ранее
найденной вершиной и, вершина v (вместе с ребром (u, v)) добавляется к де-
реву поиска, становясь ребёнком (child) вершины и, а и становится родителем
(parent) v. Каждая вершина обнаруживается только однажды, так что двух ро-
дителей у неё быть не может. Понятия предка (ancestor) и потомка (descendant)
определяются как обычно (потомки – это дети, дети детей, и т. д.). Двигаясь
от вершины ккорню, мы проходим всех её предков.

Приведённая ниже процедура BFS (breadth-first search – поиск в ширину)
использует представление графа G = (V, Е) списками смежных вершин. Для
каждой вершины и графа дополнительно хранятся её цвет color[u]и её пред-
шественник [u]. Если предшественника нет (например, если и = s или и ещё
не обнаружена), [u] = NIL. Кроме того, расстояние от s до и записывается
в поле d[u]. Процедура использует также очередь Q(FIFO) для
хранения множества серых вершин.

В строках 1 – 4 все вершины становятся белыми, все значения d бесконечны-
ми, и родителем всех вершин объявляется NIL. Строки 5 – 8 красят вершину s в
серый цвет и выполняют связанные с этим действия: в строке 6 расстояние d[s]
объявляется равным 0, а в строке 7 говорится, что родителя у s нет. Наконец,
в строке 8 вершина s помещается в очередь Q, и с этого момента очередь будет
содержать все серые вершины и только их.

Основной цикл программы (строки 9 – 18) выполняется, пока очередь непус-
та, то есть существуют серые вершины (вершины, которые уже обнаружены,
но списки смежности которых ещё не просмотрены). В строке 10 первая такая
вершина помещается в и. Цикл for в строках 11 – 16 просматривает все смежные
с ней вершины. Обнаружив среди них белую вершину, мы делаем её серой
(строка 13), объявляем и её родителем (строка 15) и устанавливаем расстояние
равным d[u] + 1 (строка 14). Наконец, эта вершина добавляется в хвост очере-
ди Q (строка 16). После этого уже можно удалить вершину и из очереди Q,
перекрасив эту вершину в черный свет (строки 17 – 18).

Рисунок 5.1 – Поиск в ширину