Лекция № 15. Else{вершина t использована}

End

End

End

End

else {вершина t использована}

t Ü СТЕК,

end;

Головная программа имеет такую же структуру, что и для рекусивного варианта.

Алгоритм поиска в ширину (очередь – queue)

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

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

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

procedure BREADTH(v);

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

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

while ОЧЕРЕДЬ <> Æ do

begin p Ü ОЧЕРЕДЬ; write(p);

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

if NOWY[u] then

begin ОЧЕРЕДЬ Ü u;

NOWY[u]:= False

end;

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