флеров

Поиск в ширину в графе

Теперь рассмотрим несколько иной метод поиска в графе, называемый поиском в ширину. Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована - точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины накапливаются в стеке. Поиск в ширину основывается, грубо говоря, на замене стека очередью. После такой модификации чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра всех еще непросмотренных соседей этой вершины. Вся процедура представлена ниже:

1 procedure ПОИCК_В_ШИРИНУ_В_ГРАФЕ (v);

{поиск в ширину в графе с началом в вершине v;

переменные НОВЫЙ, СПИСОК - глобальные}

2 begin

3 ОЧЕРЕДЬ := ; ОЧЕРЕДЬ  v; НОВЫЙ [v] := ложь;

4 while ОЧЕРЕДЬ   do

5 begin p  ОЧЕРЕДЬ; посетить p;

6 for u  ЗАПИСЬ [ p] do

7 if НОВЫЙ [ u] then

8 begin ОЧЕРЕДЬ  u; НОВЫЙ [ u ] := ложь

9 end

10 end

11 end {вершина v использована}

Способом, аналогичным тому, который был применен для поиска в глубину, можно легко показать, что вызов процедуры ПОИCК_В_ШИРИНУ_ В_ГРАФЕ (v) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v, причем каждая вершина просматривается в точности один раз. Вычислительная сложность алгоритма поиска в ширину также имеет порядок m+n, так как каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

Рис. 3. 4.

На рис. 3.4 представлен граф, вершины которого занумерованы (в скобках) согласно очередности, в которой они посещаются в процессе поиска в ширину.

Как и в случае поиска в глубину, процедуру ПОИCК_В_ШИРИНУ_ В_ГРАФЕ (v) можно использовать без всяких модификаций и тогда, когда список инцидентности СПИСОК [ v ], v  V, определяет некоторый ориентированный граф. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начинаем поиск.

Содержание