3.2. Поиск в ширину.

Другой метод систематического обхода вершин графа называется поиском в ширину. Он получил свое название из-за того, что при достижении во время обхода любой вершины далее рассматриваются все вершины, смежные с вершиной , т.е. осуществляется просмотр вершин "в ширину".

Рекурсивный алгоритм поиска в ширину:

при достижении во время обхода любой вершины-источника v, далее посещать все вершины, смежные с v.

Далее эти вершины сами становятся источниками, в том порядке, в котором посещались.

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

1. Поиск начинается с посещения некоторой фиксированной вершины-источника v. Она помечается как visited и заносится в список обхода.

2. Все непосещенные вершины, смежные с v, помещаются в очередь (например, в порядке возрастания номеров), помечаются как visited.

3. Вершина из начала очереди заносится в список обхода, удаляется из очереди, все ее непосещенные смежные вершины помещаются в очередь в порядке возрастания номеров.

4. Шаг 3. повторяется, пока очередь не опустеет.

В приведенном далее эскизе процедуры bfs (сокращение от breadth-first search, что обозначает "поиск в ширину"), реализующей рекурсивный алгоритм поиска в ширину, посещенные вершины графа заносятся в очередь .

Также применяются заранее определенные функции работы с очередями:

FRONT(Q) – возвращает первый элемент очереди (front).

ENQUEUE(x, Q) – помещает элемент x в конец очереди Q.

DEQUEUE(x, Q) – удаляет первый элемент очереди (front).

EMPTY(Q) – возвращает значение 1, если очередь Q пуста, и 0 в противном случае.

Массив mark (метка) отслеживает состояние вершин: если вершина пройдена, то элемент mark[v] принимает значение visited (посещалась), первоначально все элементы этого массива имеют значение unvisited (не посещалась). Отметим, что в этом алгоритме во избежание повторного помещения вершины в очередь пройденная вершина помечается как visited до помещения ее в очередь. Процедура bfs работает на одной связной компоненте, если граф не односвязный, то эта процедура должна вызываться для вершин каждой связной компоненты.

procedure bfs ( v );

{ bfs обходит в ширину все вершины, достижимые из вершины v }

var

Q: QUEUE { очередь для вершин }

х, у: вершина;

begin

mark[v]:= visited;

ENQUEUE(v, Q);

while not EMPTY(Q) do begin

x:= FRONT(Q);

DEQUEUE(Q);

for для каждой вершины у, смежной с вершиной х do

if mark[y] = unvisited then begin

mark[y]:= visited;

ENQUEUE(y, Q);

end

end

end; { bfs }

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