Реферат: Поиск в ширину на графах

end

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

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 можно использовать без всяких модификаций и тогда, когда списки

1(1)

10(7)

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

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

3. Спецификация задачи

3.1 Входные и выходные данные

ver – массив вершин графа, заполняемый случайным образом целыми числами в диапазоне от 0 до 1000;

nv - массив флагов проверки вершин;

ocher – массив для организации очереди, заполняемой значениями рассматриваемых информационных вершин графа;

raz – переменная целочисленного типа, определяющая в программе размер создаваемого графа;

schet – счетчик количества сравнений в процедуре поиска;

key – вводимый с клавиатуры ключ поиска;

mgsi – переменная логического типа, разрешающая вывод списка инцидентности графа;

prosm - переменная логического типа, превращающая процедуру поиска WS в процедуру просмотра графа;

find - переменная логического типа, определяемая при нахождении искомой информационной вершины;