6.9. Поиск в ширину как система исследования графа

Поиск в ширину имеет отправной узел X, а процесс его представляет как бы волну, распространяющуюся в графе от "точки возмущения" X и захватывающую все новые узлы. После узла X обрабатываются все узлы, смежные с X - "дети" X, затем "дети детей" - "внуки" X и т.д. В конце концов, в связном графе все узлы, "поколение за поколением" будут обработаны. Дисциплина обслуживания - FIFO (см. п.1.5), поэтому узлы заносятся в очередь О. Признаком завер­шения поиска в ширину является исчерпание очереди О.

Повторное рассмотрение узла исказило бы систему; чтобы этого из­бежать, посещенные узлы j снабжаются признаком Rj 0. Изна­чально вектор R содержит нули. Таковы две используемые струк­туры. В качестве Rj можно записывать "отца" узла j: вектор призна­ков R заодно будет представлять широтный каркас. В нем узлы одно­го поколения занимают ярус. Хорда либо связывает узлы одного яруса, либо узлы 2 соседних ярусов.

Если применить поиск в ширину к графу G1 (п.5.4), будет построена очередь

5 3 8 9 2 4 7 1 6

узел X дети внуки правнуки сформирован широтный каркас:

В несвязном графе процесс заканчивается после посещения всех узлов одной компоненты связности. Поэтому поиск в ширину можно использовать для проверки связности графа и выделения компонент связности.

Пример 6.9.

Применим поиск в ширину к графу G1, начиная с узла 1.

Constn=9; {Значение п не должно превышать 254}

Type matr=Array [1..n,1..n] of byte; vek=Array[1..n] of byte;

Const A: matr = ( (0,1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0),

(1,0,1,0,0,0,1,0.0),

(0,0,1,0,0,0,0,1,1),

(0,1,0,0,0,0,0,0,0),

(0,0,1,1,0,0,0,0,0),

(1,0,0,0,1,0,0,0,0),

(0,0,0,0,1,0,0,0,0) );

Var O:vek;j,k:byte;

Procedure Svjaz (Var A:matr; Var O:vek; Var k:byte);

Var R:vek; i,j,L:byte;

Begin For j:=1 to n do R[j]:=0;

i:=1; k:=1; {/ - указатель головы, k - конца очереди}

O[k]:= 1; {Заносим в очередь отправной узел}

R[1 ]:= n+1; (Отмечаем посещение узла 1}

RepeatL:= O[i]; {Номер L текущего узла берем из очереди}

Forj:=1 tondoIf (A[L,j] <>0) And (R[j] = 0) Then BeginR[j]:=L; k:=k+1; O[k]:=jEnd; {Ставим "сына" jузла L в очередь} i:=i+1 {Переходим к следующему "отцу", пока не опустеет очередь}

Until i > k

End;

BEGIN Svjaz (A, O, k);

If k=n Then Writeln ('Граф G1 - связный')

Else Begin Write ('Узлы 1-йкомпоненты: ', O[1]);

For j:=2 to k do Write (', ', 0[j]); Writeln End; Readln;

END.

Сложность поиска в ширину при нематричном представлении графа равна O(n+m), ибо рассматриваются все n узлов и m ребер. Использование матрицы смежности приводит к оценке О(n² ).

В широтном каркасе любой узел связан с потомками кратчайшими цепями, что и обусловливает область применений поиска в ширину.

Рассмотрим ряд понятий. Расстояние r_ij между v_i , v_j - это длина кратчайшей цепи, ведущей от v_i к v_j , а диаметр графа - наибольшее из значений r_ij . Эксцентриситет е_j узла j - расстояние от узла до наиболее удаленного от него узла. Диаметр графа является наибольшим из эксцентриситетов, а радиус графа - наименьшим. Ес­ли узел jнедостижим от узла i, считают, что r_ij =  .

В связном графе медиана - это узел, сумма расстояний от которого до прочих узлов минимальна. У периферийного узла эксцентриситет равен диаметру, а у центрального - радиусу. Множество цен­тральных узлов называют центром графа. Назовем S-периферией (S-окружением) узла j множество узлов, расстояние до которых боль­ше S (не больше S). Нахождение всех указанных характеристик вы­полняют с помощью поиска в ширину. Еще одно весьма важное применение рассмотрим в п.5.15.

Задание 6.9.

• 1. Испытайте программу примера 5.9 на несвязном графе.

2. Реализуйте пример 5.9, используя для описания графа G1 струк­туру с оглавлением. Обдумайте изменения, необходимые для отраже­ния в массиве О

всех компонент связности графа.