Деревья и графы
Деревья находят широкое применение при проектировании алгоритмов и, в частности, структур данных. Отсылая читателя к литературе по теории графов, мы будем пользоваться такими понятиями, как узел, ребро, лист, потомок, сын, левый потомок, правый потомок, предок, отец, корень, ветвь и другие. Регулярным деревом назовем дерево, в котором фиксировано максимально возможное (как правило, небольшое) число потомков для каждого из его узлов. В частности, если число потомков для каждого узла не больше двух, то дерево называется бинарным, если не более трех — тернарным. Если это число может равняться только двум или трем, то дерево называется (—)-деревом.
Достаточно универсальным является способ представления регулярных деревьев, при котором каждый узел представляется записью, содержащей, кроме прикладной информации, позиции смежных с ним элементов, например позиции потомков или наряду с потомками позицию предка или еще каких-либо узлов, в зависимости от потребностей. Регулярность дерева позволяет фиксировать число полей, достаточное для представления любого узла.
Так, узлы бинарного корневого дерева можно представлять записями вида
где представляет связанную с узлом прикладную информацию, — позицию его левого потомка, а — позицию правого потомка. Само дерево в таком случае можно представить позицией его корня. Если в алгоритме необходимо продвижение от узла к предку, то узлы бинарного корневого дерева можно представлять записями вида
где — позиция предка рассматриваемого узла.
Для представления нерегулярных деревьев (то есть деревьев, узлы которых могут иметь произвольное число потомков) применяют следующий способ: потомки каждого узла нумеруются и каждый узел представляется записью, включающей в себя позицию его первого (левого) потомка и позицию его "правого брата".
Для регулярных деревьев более экономным по памяти может оказаться представление с помощью массива. Рассмотрим этот прием на примере бинарного дерева. Значения индексов массива отождествляются с узлами дерева, пронумерованными так, что корень получает номер 1, а потомки узла c номером получают номера и .
При таком представлении предок узла с номером будет иметь номер
(частное от деления на 2). Аналогично можно представить тернарное и другие регулярные деревья.
Остановимся вкратце на представлении графов общего вида. Обыкновенный граф с вершинами часто представляют матрицей смежности, то есть матрицей размером , в которой элемент, расположенный в -й строке и -м столбце, равен , если вершины графа с номерами , соединены ребром, и равен 0, если такого ребра нет. Если граф не ориентирован, то его матрица смежности симметрична и можно ограничиться хранением ее треугольной части.
Матричный способ представления может оказаться неэкономным с точки зрения использования памяти, если граф разрежен. Так, например, известно, что число ребер связного планарного графа с вершинами не превосходит величины () при , то есть оценивается величиной , а не как в общем случае . Представлять такие графы матрицей смежности, как правило, нецелесообразно.
Другой способ представления графа — это список или массив пар вершин, соответствующих ребрам. При таком способе, если граф не ориентирован, то из двух возможных пар (, ) и (, ) целесообразно хранить только одну, например ту, у которой первая компонента меньше второй.
Еще один способ, часто имеющий преимущества перед названными выше, — это представление графа массивом или списком списков (рис. 2.7).
Рис. 2.7. Представление графа комбинацией списков: множество вершин представлено списком узлов, к каждому из которых справа подцеплен список смежных с ним вершин
А именно, для каждой вершины организуется список смежных с ней вершин. В этом случае легко осуществляется доступ к окрестностям вершин. Примерно такого же эффекта можно достичь, представляя граф с помощью двух массивов: и , где — число ребер графа. Массив назовем адресным, а — информационным. В информационном массиве вначале перечисляются номера вершин, смежных с первой вершиной, затем — со второй и так далее. В адресном массиве указываются номера позиций информационного массива так, чтобы для каждой вершины по ним можно было находить фрагменты массива , в которых записаны номера вершин, смежных с этой вершиной.Например, может хранить позицию, с которой начинаются в массиве
вершины, смежные с -й, при этом
— первая позиция за пределами массива . В таком случае, если нам требуется с каждой вершиной из окрестности вершины выполнить оператор , то можно сделать это с помощью оператора цикла:
Заметим, что если граф не ориентирован, то каждое ребро (, ) будет представлено дважды: один раз в последовательности вершин, смежных с вершиной , а второй раз — в последовательности вершин, смежных с вершиной . Но эта избыточность часто бывает полезна с точки зрения времени выполнения операций над окрестностями вершин графа. Как недостаток такого представления графа, можно отметить неудобство при динамической модификации графа, например, добавление к графу ребра может потребовать большого количества пересылок в массиве . Этого недостатка лишен способ представления графа, показанный на рис. 2.7.
