Алгоритм поиска в ширину

Основная идея такого поиска – последовательный просмотр списков инцидентности вершин, смежных с данной. При поиске в ширину, попав в новую вершину, просматривают все смежные с ней непросмотренныевершины и заносит их в список, после чего эта вершина считается обработанной. Далее переходят в новую вершину, стоящую первой в списке необработанных вершин. Иными словами, просмотр осуществляется по принципу очереди: чем раньше вершина просмотрена, тем раньше она будет обработана.

Например, для графа, изображенного на рис. 5, последовательность просмотра вершин с помощью поиска в ширину имеет вид: 1, 2, 4, 7, 5, 6, 3.

Сложность реализации алгоритма в том, что рекурсивные процедуры действуют по принципу стека, а не очереди. Поэтому в этом случае возможен только нерекурсивный вариант алгоритма.

procedure BREADTH(v);

begin ОЧЕРЕДЬ ; {ОЧЕРЕДЬ – локальная структура }

ОЧЕРЕДЬ ; NOWY [ v ] False;

while ОЧЕРЕДЬ <> do

begin p ОЧЕРЕДЬ; Write (p);

for u СПИСОК [ p ] do

if NOWY [ u ] then

begin ОЧЕРЕДЬ u;

NOWY [ u ] False

end

end

end;

Как мы уже говорили, основная программа отличается от соответствующей программы поиска в глубину только именем вызываемой во втором цикле процедуры. Аналогично можно показать, что алгоритм корректен, а его вычислительная сложность также равна .

Дата добавления: 2015-06-27