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

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

Метод поиска в ширину получается из программы поиска в глубину, если заменить стек возврата на очередь. Эта простая замена модифицирует порядок обхода вершин так, что обход идет равномерно во все стороны, а не вглубь как при поиске в глубину (рис. 3).

Здесь используются те же структуры Graph и Visited, что были

описаны в алгоритме поиска в глубину.

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.

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

Поиск в ширину для полного обхода графа с n вершинами и m дугами требует столько же времени, как и поиск в глубину, т. е. времени порядка O(max(n, m)). Поскольку обычно m ≥ n, то получается O(m).