Модификации алгоритмов

End;

End

End

Procedure BREADTH( v ) ;

End;

End

T Ü СТЕК,

End

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

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

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

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

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

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

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

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

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

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

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

if NOWY[u] then

begin ОЧЕРЕДЬ Ü u;

NOWY[u]:= False

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

С помощью алгоритмов поиска в глубину и в ширину легко решаются следующие задачи:

1. Определение числа связных компонент графа.

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

2. Поиск маршрута (пути) между двумя фиксированными вершинами u и v и определение его длины.

Маршрут (путь) строится с помощью любого алгоритма поиска. Поиск начинается из вершины u и продолжается, пока не встретится вершина v или не произойдет возврат в основную программу. Если после возврата из процедуры вершина v не найдена, значит нужного маршрута (пути) не существует, и задача не имеет решения.