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

Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На 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 – Поиск в ширину