6.3. Другие представления графов

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

Списки инцидентности. Для каждого узла создается цепной список, в котором - отдельными элементами - указаны узлы, смежные с данным узлом. Головы списков образуют массив ссылок, где порядковый номер ссылки соответствует номеру данного (головного) узла. Ниже показана подобная структура для графа G из п.5.1:

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

Структура с оглавлением. Если граф статичен, т.е. связи узлов неизменны, выгоднее ссылки изъять, показанные выше перечни узлов "уложить" в общий массив, а границы перечней указать в оглавлении. Для графа G из п.5.1 подобная структура показана ниже:

Элемент og[j] оглавления указывает, где в массиве начинается перечень узлов, смежных с j-м узлом, одновременно являясь границей предыдущего перечня (поэтому и понадобился последний элемент og[7] = 15). Массив содержит 2*m элементов, оглавление - n + 1 эле­мент. Для изолированного узла начало перечня совпадет с началом следующего перечня, т.е. его перечень - пуст.

Мы упорядочили перечни, и вот почему: проверка, существует ли ребро {i, j}, является типичным действием; в неупорядоченном перечне i-го узла эта проверка выполняется перебором, т.е. медленно, а в упорядоченном перечне возможен дихотомический (быстрый) поиск.

Структура с оглавлением не проигрывает (по расходу памяти) матрице смежности - двумерному массиву даже в случае полного графа.

Описание графа в виде перечня ребер менее выгодно и здесь не рассматривается.

Задание 6.3.

• Реализуйте пример 5.1, используя для описания графа структуру с оглавлением.

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

По-видимому, исследование графа (лабиринта) мифическим героем Тесеем с целью убийства Минотавра является первым успешным приме­нением поиска с возвращениями (см. п.1.12) на графах, называемого поиском в глубину^*.

Исчерпывающее исследование графа требуется и во многих реаль­ных задачах. Поиск в глубину основывается на простых идеях:

а) если среди узлов, смежных с данным узлом, есть непосещенный узел, переходим к нему и снова делаем шаг “а”;

и н а ч е

б) возвращаемся к предыдущему (пройденному) узлу для очередного вы­полнения шага "а ".

Характер действий, выполняемых в узле зависит от задачи.

Рано или поздно последовательность шагов "а", "б" приведет к тому, что вместо шага "б" произойдет выход из графа. К этому моменту все узлы связного графа будут посещены.

Итак, мы не рассматриваем все смежные узлы, а выбирая один, бы­стро продвигаемся вглубь, откладывая их посещение "на потом".

Шаг "а" назовем "шагом вперед", шаг "б" - "шагом назад". Узел, от которого делаем шаг вперед, назовем "отцом", а в который прихо­дим - "сыном"; узлы, посещенные вслед за "сыном" вплоть до воз­вращения к "отцу", уместно назвать его "потомками".

Как это следует из описания шага "а", при движении вперед узел может быть посещен лишь однажды. Воспользуемся изображенным ниже графом G1, отправным узлом X сделаем узел 5:

В терминах графов поиск в глубину (вариант "а") описывается так: начиная от узла X строим простую цепь поиска, пока ее удается продлить (в графе G1 цепь 5, 3, 2, 1, 4, 7; сделано 5 шагов вперед), затем возвращаемся (2 шага) - по той же цепи, стирая звенья (7, 4), пока не найдем узел (1), имеющий н е п о с е щ е н н ы й смежный узел 8. Узел 1 становится отправным для наращивания цепи поиска (5, 3, 2, 1, 8; снова "тупик"). Опять идет возврат, теперь до узла 2, у которого обнаруживается непосещенный "сосед" 6 (воз­никает цепь 5, 3, 2, 6; "тупик"). От узла 6 возвращаемся к узлу X (3 шага), но это еще не конец, ибо у X есть непосещенный "сосед" 9; строится цепь 5, 9. Возврат по ней и приводит к выходу из графа.

Легко понять, что совокупность указанных простых цепей (дерево поиска) образует каркас связного графа, который будем называть глубинным. В нем два узла, соединенные хордой, всегда принадлежат одной и той же простой цепи поиска, т.е. не могут быть в разных ветвях каркаса. Листья каркаса назовем терминальными узлами (в G1 - 7, 6, 8, 9).

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

При посещении узел j снабжается признаком Rj = 1, чтобы впредь отличать его от непосещенных, признак которых изначально равен 0. Совокупность Rj - это массив, числовой или логический.

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

Пример 6.3.

Приближаясь к решению задачи нахождения множества фундамен­тальных циклов, построим каркас связного графа. На каждом шаге вперед для нового текущего узла будем запоминать его "отца". Для этого можно применить элемент Rj, если договориться посещение узла обозначать значением Rj, не равным нулю. Совокупность всех Rj в итоге представит каркас графа. В этом представлении можно будет продвигаться только к корню каркаса. Построим каркас графа G1, затем проверим одну из простых цепей, входящих в каркас:

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 R:vek; j:byte;

Procedure Karkas(Var A:matr; X:byte; Var R:vek);

Var St:vek; c:Boolean; j,k,L:byte;

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

k:=1; {k - указатель верхушки стека}

St[k]:= X; {Занесение в стек st отправного узла}

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

j:=0;

RepeatL:= St[k]; {Номер L текущего узла берем из стека}

с:= false; {Далее идет цикл поиска смежного узла}

Repeat j:=j+1;

If j > n Then c:= true

Else If (A[L,j]=1) And (Rfj]=0) Then c:=true

Until с; {Или смежный узел найден,или L-я строка исчерпана}

Ifj>nThen {Шаг назад, ибо L-я строка исчерпана: }

Beginj:=L;k:=k-1 End{Перемещаем верхушку стека}

Else {Шаг вперед, ибо подходящий смежный узел найден:}

Begink:=k+1;St[k]:=j; {Заносим в стек новый узел j}

R[J]^:=L;{Отмечаем посещение узла j и запоминаем "отца"}

j:=0

End

Until k = О

End;

BEGIN Karkas(A, 5, R); {Находимкаркасграфа G1 для X=5}

j:=8; {Далее проверяем простую цепь, ведущую от Х к узлу 8}

RepeatWrite(j,', '); j:= R[j] {Продвижение к "отцу" узла j}

Until j = n+1; Writeln; Readln;

END.

В блоке Karkas через L обозначен текущий узел, через - очередной, "кандидат" на эту роль. Возвращаясь к некоторому узлу Y, мы не должны рассматривать все смежные узлы, а продолжать анализ его связей. Неприметное действие j:=L (выделено в программе), выполняемое при возврате к Y, восстанавливает номер столбца, на котором мы остановились, уходя от узла Y "вперед". Теперь анализироваться будут лежащие правее элементы Y-й строки матрицы А.

Если граф не связен, поиск в глубину ограничивается компонентой графа связности, в которой выбрали отправным узел X. При этом элементы R[j], относящиеся к узлам j других компонент, сохраняют исходное значение 0. Чтобы продолжить поиск в новой компоненте, надо взять отправной узел j, для которого R[j]=0.

Задание 6.4.

• Реализуйте пример 5.3, используя как описание графа структуру соглавлением.