Анализ алгоритма. 
Модели систем. 
Графы

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

• 1 procedure WS (v);
• (*поиск в ширину в графе с началом в вершине v;

переменные НОВЫЙ, ЗАПИСЬ — глобальные *).

• 2 begin
• 3 ОЧЕРЕДЬ := ?; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь
• 4 while ОЧЕРЕДЬ? ? do
• 5 begin р<= ОЧЕРЕДЬ; посетить р;
• 6 for u? ЗАПИСЬ [р] do
• 7 if НОВЫЙ [u] then
• 8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]: =ложь
• 9 end
• 10 end
• 11 end

Примечание: в 7-й строке псевдокода кроме условия НОВЫЙ[u] должно также выполниться условие наличия связи (ребра) между v-й и u-й вершинами. Для установки наличия ребра сначала в списке v-й вершины ищется информационное значение u-й вершины. Если оно найдено, то ребро установлено, если нет, то информационное значение v-й вершины ищется в списке u-й вершины, т. е. наоборот. В результате добавления двух лишних циклов поиска общий алгоритм поиска несколько теряет компактность, но на быстродействии в целом это не сказывается.

• 1 procedure Write_S;
• 2 begin
• 3 for v? V do НОВЫЙ[u]: = истина; (* инициализация *)
• 4 for v? V do
• 5 if HOBЫЙ[v] then WG (v)
• 6 end

Способом, аналогичным тому, какой был применен для поиска в глубину, можно легко показать, что вызов процедуры WS (v) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v, причем каждая вершина просматривается в точности один раз. Вычислительная сложность поиска в ширину также имеет порядок О (m + n), так как каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

В очереди помещены сначала вершины, находящиеся на расстоянии 0 от v (т. е. сама вершина v), затем поочередно все новые вершины, достижимые из v, т. е. вершины, находящиеся на расстоянии 1 от v, и т. д. Под расстоянием здесь мы понимаем длину кратчайшего пути. Предположим теперь, что уже рассмотрели все вершины, находящиеся на расстоянии, не превосходящем r, от v, что очередь содержит все вершины, находящиеся от v на расстоянии r, и только эти вершины. Использовав каждую вершину р, находящуюся в очереди, наша процедура просматривает некоторые новые вершины, и каждая такая новая вершина u находится, очевидно, на расстоянии г + 1 от v. После использования всех вершин из очереди, находящихся на расстоянии r от v, она (очередь), очевидно, содержит множество вершин, находящихся на расстоянии r + 1 от v, и легко заметить, что условие индукции выполняется и для расстояния r + 1.

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

Как и в случае поиска в глубину, процедуру WS можно использовать без всяких модификаций и тогда, когда списки инцидентности ЗАПИСЬ[v], v = V, определяют некоторый ориентированный граф. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начинаем поиск.

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