Графы и их представление

Известно [10] несколько представлений графа G=(V, E), где V – множество вершин, Е - множество ребер. Одно из них - матрица смежностей, т. е. матрица А размера | V |*| V |, состоящая из 0 и 1, в которой A[ i, j ]=1 тогда и только тогда, когда есть дуга из узла i в узел j. Представление в виде матрицы смежности удобно для тех алгоритмов на графах, для которых часто нужно знать, есть ли в графе данная дуга, ибо время, необходимое для определения наличия дуги, фиксировано и не зависит от |V| и |E|.

Основной недостаток применения матрицы смежностей заключается в том, что она занимает память |V|² даже тогда, когда граф содержит только О(|V|) дуг. Уже начальное заполнение матрицы смежностей посредством "естественной" процедуры требует времени О(|V|²), что сводит на нет алгоритмы сложности О(|V|) при работе с графами, содержащими лишь О(|V|) дуг. Поэтому алгоритмы сложности О(|V|), основанные на работе с матрицей смежностей, встречаются редко.

Интересной альтернативой является представление строк и (или) столбцов матрицы смежностей в виде двоичных векторов. Такое представление может способствовать значительной эффективности алгоритмов на графах.

Еще одно представление графа - с помощью списка. Списком смежностей для узла V называется список всех узлов W, смежных с V. Граф можно представить с помощью | V | списков смежностей, по одному для каждого узла.

Пример 3.2. На рис. 3.8,а изображен орграф, содержащий четыре узла, а на рис. 3.8,б - его матрица смежностей. На рис. 3.8,в показаны четыре списка смежностей, по одному для каждого узла. Например, из узла 1 в узлы 2 и 4 идут дуги, так что список смежностей для узла 1 содержит
компоненты 2 и 4, связанные в смысле рис. 3.1.

Табличное представление списка смежностей показано на рис. 3.8,г. Каждая из первых четырех ячеек в массиве NEXT содержит указатель на первый узел списка смежностей, а именно NEXT[ i ] указывает на первый узел списка смежностей для узла i.

Заметим, что NEXT[3]=0, поскольку в списке смежностей для узла 3 нет узлов. Остальные составляющие массива NEXT представляют дуги графа. Массив END содержит узлы из списков смежностей. Таким образом, список смежностей узла 1 начинается в ячейке 5, ибо NEXT[1]=5, END[5]=2; это показывает, что есть дуга (1,2). Равенства NEXT[5]=6 и END[6]=4 означают, что есть дуга (1,4), а NEXT[6]=0, что больше нет дуг, начинающихся в узле 1.

Заметим, что представление графа в виде списков смежностей требует памяти порядка |V| + |E|. Таким представлением часто пользуются, если |E|<<|V|².

Если граф неориентирован, то каждое ребро (v,w), т. е. дуга с двумя противоположными направлениями, представляется дважды: один раз в списке смежностей для v и один раз в списке смежностей для w. В этом случае можно добавить новый массив, называемый CON (CONjuction – соединение, связь), чтобы корректировать оба экземпляра неориентированной дуги. Таким образом, если i -я ячейка, соответствующая узлу w в списке смежностей для v, то CON[i]- ячейка, соответствующая узлу v в списке смежностей для w.

Если необходимо с удобством удалять рёбра из неориентирован-ного графа, то списки смежностей можно связать дважды (подразд. 3.1). Это обычно бывает нужно потому, что даже если удалять всегда ребро (v, w), стоящее первым в списке смежностей узла v, всё равно может оказаться, что ребро, идущее в обратном направлении, стоит в середине списка смежностей узла w. Чтобы быстро удалить ребро (v, w) из списка смежностей для w, надо уметь быстро находить ячейку, содержащую предыдущее ребро в этом списке смежностей.

 

Деревья и их представление

 

Определения и свойства

Определение. Конечное корневое дерево T - это непустое множество упорядоченных узлов, таких что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на m 0 поддеревьев Т₁,Т₂,...,Т_m. Узлы, не имеющие поддеревьев, называются листьями; остальные узлы называются внутренними.

Пример 3.3. На рис. 3.9 изображено дерево с одиннадцатью узлами, помеченными буквами от А до К. Узлы с метками D, E, F, H, J и K являются листьями; другие узлы внутренние. Узел А - корень.

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

Для описания соотношений меж-ду узлами дерева используется тер-минология, принятая в генеалогиче-ских деревьях.

 

Так, в дереве (или поддереве) все узлы являются потомками его корня, и наоборот, корень - предок всех своих потомков. Корень именуется отцом корней его поддеревьев, которые в свою очередь будут сыновьями корня. На рис. 3.9 узел А является отцом узлов B, G и I; J и K - сыновья I, а C, E, F - братья; пунктиром выделено поддерево с узлами I, J, K.

Все рассматриваемые деревья будут упорядочены, т.е. для них будет важен относительный порядок расположения следования каждого узла. Таким образом, деревья, представленные на рис. 3.10,а и б, счи-таются различными.

Для дерева вводятся следующие характеристики:

· глубина узла v в дереве - это длина пути из корня в v;

· высота узла в дереве - это длина самого длинного пути из v в какой-нибудь лист;

· высотой дерева называется высота его корня;

· уровень узла v в дереве равен разности высоты дерева и глубины узла v.

Например, на рис. 3.9 высота дерева равна 3; узел К имеет глубину 2, высоту 0 и уровень 1.

Определение. Лес - упорядоченное множество деревьев. В связи с этим можно переопределить понятие дерева: дерево есть непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с m 0 поддеревьями корня.

Важной разновидностью корневых деревьев является класс бинарных (двоичных) деревьев.

Определение. Бинарное дерево Т либо пустое, либо состоит из выделенного узла, называемого кор-нем, и двух бинарных поддеревьев: левого Т₁ и правого T₂. Бинарные деревья не являются подмножеством множе-ства деревьев, они полностью отличаются по своей структуре, поскольку две следующие картинки (в и г на рис. 3.10) не изображают одно и то же бинарное дерево. Как деревья, однако, они обе неотличимы от картинки д.

Различие между деревом и бинарным деревом состоит в том, что дерево не может быть пустым, и каждый узел дерева может иметь произвольное число поддеревьев; в то же время бинарное дерево может быть пустым, каждый из его узлов может иметь 0, 1 или 2 поддерева, и существует различие между левыми и правыми поддеревьями.

Определение. Бинарное дерево называется полным, если для некоторого целого k каждый узел глубины меньше k имеет как левого, так и правого сына, а каждый узел глубины k является листом. Полное бинарное дерево высоты k имеет ровно 2 ^{k +1}–1 узлов.

Определение. Неориентированным деревом называется неориен-тированный ациклический связанный (любые два узла соединены путем) граф. Корневое неориентированное дерево - это неориентированное дерево, в котором узел выделен в качестве корня.

Ориентированное дерево можно превратить в корневое неориен-тированное, просто сделав все его ребра неориентированными. Обычно используют одну и ту же терминологию и применяют одни и те же обоз-начения для корневых неориентированных и ориентированных деревьев. Основное математическое различие здесь состоит в том, что все пути в ориентированном дереве идут от предков к потомкам, тогда как в корне-вом неориентированном дереве пути могут идти в обоих направлениях.

 

Представление деревьев

 

Почти все машинные представления деревьев основаны на связанных распределениях, при этом каждый узел состоит из поля INFO и нескольких полей для указателей. Например, одно из представлений для каждого узла имеет единственное поле для указателя F (Father – отец) на отца данного узла. При этом приведенное на рис. 3.8 дерево будет выглядеть так, как показано на рис. 3.11.

Такое представление полез-но, если необходимо подниматься по дереву от потомков к предкам. Однако эта операция встречается довольно редко; чаще требуется спуститься по дереву от предков к потомкам.

Представление дерева (или леса) с использованием указате-лей, ведущих от предков к потомкам, довольно сложно, поскольку узел, имея не более одного отца, может иметь в то же время произвольно много сыновей. Другими словами, при таком представлении узлы должны различаться по размеру, что является определённым неудобством. Один из путей обхода этой трудности состоит в том, чтобы определить соотношение между деревьями и бинарными деревьями, поскольку бинарные деревья легко представить узлами фиксированного размера. Каждый узел в этом случае имеет три поля: LEFT (указывает положение корня левого поддерева), INFO (содержимое узла) и RIGHT (указатель местоположения корня правого поддерева). Всё сказанное выше проиллюстрировано на рис. 3.12.

Деревья можно изобразить как бинарные (используя узлы фикси-рованного размера), представляя каждый узел леса в виде узла бинарного дерева, состоящего из полей LEFT, INFO и RIGHT. При этом поле LEFT предназначается для указания самого левого сына данного узла, а поле RIGHT – для указания следующего брата этого узла.

Таким образом, поле LEFT некоторого узла используется для указателя на связанный список сыновей этого узла; этот список связывается с помощью полей RIGHT. Такое представле-ние называется естественным соответствием между лесами и бинарными деревьями.

Бинарное дерево обычно представляют в памяти машины в виде двух массивов LES (LEftSon - левый сын) и RIS (RIghtSon - правый сын). Пусть узлы бинарного дерева зануме-рованы целыми числами от 1 до N. В этом случае LES[ i ]= j тогда и только тогда, когда узел с номером j является левым сыном узла с номером i. Если у узла i нет левого сына, то LES[ i ]=0. RIS[ i ] определяется аналогично. Узел i, у которого LES[ i ] = 0, является листом. Братьями являются узлы i, j, k, для которых имеет место соотношение RIS[ i ] = j, RIS[ j ] = k.

Полное бинарное дерево высоты k часто представляют одним массивом. В позиции 1 этого массива находится корень. Левый сын узла в пози-ции i расположен в позиции 2 i, а его правый сын - в позиции [ i /2].

 

Рассмотрим на конкретном примере преобразование дерева (леса) в бинарное дерево, используя естественное соответствие между ними, а также приведём представление бинарного дерева в памяти ЭВМ.

 

Пример 3.4. Задан лес (рис. 3.13, а). Преобразуем его в бинарное дерево, для чего выстроим всех братьев в горизонтальные линии, которым будут соответствовать связанные списки братьев; при этом корни всех деревьев леса считаются также братьями. В результате такого преобразо-вания получим бинарное дерево, показанное на рис.3.13,б.

Теперь можно полученное бинарное дерево представить в виде массивов LES и RIS, сведенных в таблицу. На рис. 3.14 приведен фрагмент этой таблицы, причём в качестве индексов массивов в ней ис-пользуются имена узлов, расположенных в алфавитном порядке. Видно, что например узел С является отцом, у которого самый левый сын – узел D, а остальные сыновья (E и F) рассматриваются как следующие братья узла D. В то же время соотношение RIS[C]=G говорит о том, что узел G является братом для узла C; если теперь посмотреть на строку G, то можно увидеть ещё одного брата узлов C и G - узел H. Нули в массиве LES для строк с индексами D, E, F, G означают, что узлы с теми же именами не имеют сыновей; в строке с индексом F имеем RIS[F]=0, т.е. узел F не имеет следующего брата.

 

LES RIS
A	B	M	Если переименовать узлы рассматри-ваемого леса, т.е. ввести вместо букв их но-мера в алфавитном порядке, то можно убедиться, что эти номера подчиняются приведенным выше соотношениям. Так, LES[3]=4 и LES[4]=0 (C®3, D®4), т.е. узел 4 является самым левым сыном узла 3, а узел 4 не имеет сыновей.
B		C
C	D	G
D		E
E		F
F
G		H
H	I
…	…	…
Рис.3.14. Представле- ние бинарного дерева

 

В заключение рассмотрим пример представления арифметического выражения с помощью бинарного дерева.

Пример 3.5. Арифметическое выражение с операциями +, -, ´, ¤ может быть очевидным образом представлено бинарным деревом, если в качестве операторов взять внутренние узлы, а операндами считать листья. Например, выражению ((A+B)/C - D) ´ E соответствует следующее дерево (рис. 3.15).

Прохождение леса

 

Во многих приложениях необхо-димо пройти лес (например, в алгоритмах, построенных на деревьях, решается задача нахождения корня дерева), посещая все его узлы в определённом порядке и обрабатывая их некоторым систематическим образом.

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

Представляются полезными следующие 4 основных способа прохождения леса в некотором порядке, а именно: в прямом (в глубину), обратном (снизу вверх), в горизонтальном (в ширину) и для бинарных деревьев – во внутреннем (симметричном или лексикографическом).

Прохождение в прямом порядке полезно в процедурах поиска.

Заметим, что прохождение леса в прямом порядке в точности такое же, как и прохождение в прямом порядке бинарного дерева, являющегося его представлением. Этот факт делает ²естественным² соответствие между деревом и бинарным деревом.

Обратный порядок полезен, в частности потому, что он позволяет вычислять рекурсивно определённые функции на лесах.

При горизонтальном обходе узлы леса проходятся слева направо, уровень за уровнем, от корня вниз. Такое прохождение дерева полезно в определённых алгоритмах на графах.

Рассмотрим три широко распространённых способа прохождения дерева: в прямом, обратном и внутреннем порядке.

Определение. Пусть Т - дерево с корнем r и сыновьями v₁, v_k, k 0. При k =0 это дерево состоит из единственного узла r. Тогда прохождение дерева определяется следующими рекурсиями.

В прямом порядке:

1) посетить корень r;

2) посетить в прямом порядке поддеревья с корнями v₁,..., v_k в указанной последовательности.

В обратном порядке:

1) посетить в обратном порядке поддеревья с корнями v₁,..., v_k в указанной последовательности;

2) посетить корень r;

Во внутреннем порядке:

1) посетить во внутреннем порядке левое поддерево корня (если оно существует);

2) посетить корень r;

3) посетить во внутреннем порядке правое поддерево корня (если оно существует).

Если при некотором прохождении дерева его узлам были присвоены какие-то номера, то на узлы удобно ссылаться по этим номерам. Так, v будет обозначать узел, которому был присвоен номер v. Если все узлы занумерованы в порядке посещения, то рассмотренные нумерации обладают рядом интересных свойств.

При нумерации в прямом порядке все узлы поддерева с корнем r имеют номера, не меньшие r. Точнее, если D_r - множество потомков узла r, то v будет номером некоторого узла из D_r тогда и только тогда, когда r£v < r +ïD_rï.

Поставив в соответствие каждому узлу его номер в прямом порядке и количество его потомков, легко определить, является ли некоторый узел w потомком для v, причём за фиксированное время, не зависящее от размера дерева. Номера, соответствующие обратному порядку, обладают аналогичными свойствами.

Номера узлов дерева, соответствующие внутреннему порядку, обладают таким свойством, что номера узлов в левом поддереве для v меньше v, а в правом поддереве больше v. Таким образом, чтобы найти узел с номером w, надо сравнить w с корнем r. Если w=r, то искомый узел найден. Если w<r, то надо повторить этот процесс для левого поддерева; если w>r, то повторить процесс для правого поддерева. В конце концов узел с номером w будет найден.

Пример 3.6. На рис. 3.16 изображено двоичное дерево, узлы которого пронумерованы в соответствии с прохождением его различным образом.

 

Отметим, что алгоритм прохождения во внутреннем порядке подробно рассматривается в следующей главе.

Заключение

Данные, прежде чем подвергнутся обработке в машине, проходят две стадии структурирования: сначала выбираются (строятся) их матема-тические модели (математические структуры, или абстрактные типы данных по [7]), а затем они трансформируются в структуры, удобные для представления в памяти машины (машинные структуры).

Необходимость в машинных структурах данных определяется особенностью организации оперативной памяти (ОП) – доступ к ячейкам памяти является произвольным, а ячейки нумеруются подряд. Поэтому естественным является расположение в ОП подряд некоторой совокуп-ности данных – это последовательное распределение, характерное для статических структур данных. Если же нужно изменять количество данных в совокупности, то удобнее данные в ОП располагать произвольно, но они должны быть связаны в совокупность с помощью указателей на следу-ющее данное – это связанное распределение, характерное для динами-ческих структур данных.

В соответствии с формулой Н. Вирта [6] для построения эффек-тивного алгоритма требуется выбрать подходящие структуры данных; этот выбор определяется операциями, которые будут проводиться над данными.

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

Списки могут иметь сложную структуру. Так, в списке каждая ком-понента может также являться списком. Возможно иерархическое постро-ение структур данных, например, в виде дерева стеков.

Время выполнения операций над списком не зависит от его длины.

Обход деревьев применяют в комбинаторных задачах; наиболее часто используются 3 способа обхода: прямой, обратный и внутренний.

Контрольные вопросы. Упражнения

1. Какую структуру данных целесообразно использовать при составлении алгоритма решения задачи поиска пути в лабиринте?

2. Какую структуру данных целесообразно использовать при составлении алгоритма решения задачи «Ханойские башни»?

3. Что общего у стека и очереди, в чём их различие?

4. Почему время выполнения операции вставки элементов в список любого вида либо удаления из него не зависит от длины списка?

5. Напишите на псевдоязыке программу печати элементов односвязного списка, используя операцию readel (чтение элемента списка без его удаления) и вспомогательный регистр RG.

6. Напишите процедуру обмена элементами в позициях p и NEXT[ p ] для односвязного списка.

7. Напишите на псевдоязыке программы вставки, удаления и обмена элементов последовательности ключей при их сортировке методом простого выбора, используя список для готовой подпоследовательности и массив – для входной подпоследовательности.

8. В условиях предыдущего упражнения используйте стек и очередь.

9. Рассмотрим многочлен вида , где b₁ > b₂ >…> b_n ³0. Такой многочлен можно представить в виде связанного списка, где каждая ячейка имеет три поля: одно – для коэффициента a_i; второе - для показателя степени b_i; третье – для указателя на следующую ячейку. Для описанного представления многочленов напишите программы их сложения, умножения, дифференцирования и интегрирования.

10. Как реализовать очередь, если её элементами являются символьные строки произвольной длины? Сколько времени необходимо для операции вставки элемента в очередь?