logo
УП_САОД_2003

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

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

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

Здесь используются те же структуры 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.

Рисунок 52. Поиск в ширину

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

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4