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