Структуры данных и модели вычислений


Деревья и графы - часть 2


При таком представлении предок узла с номером будет иметь номер

(частное от деления на 2). Аналогично можно представить тернарное и другие регулярные деревья.

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

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

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

Еще один способ, часто имеющий преимущества перед названными выше, — это представление графа массивом или списком списков (рис. 2.7).


Рис. 2.7.  Представление графа комбинацией списков: множество вершин представлено списком узлов, к каждому из которых справа подцеплен список смежных с ним вершин

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

вершины, смежные с -й, при этом

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

Заметим, что если граф не ориентирован, то каждое ребро (, ) будет представлено дважды: один раз в последовательности вершин, смежных с вершиной , а второй раз — в последовательности вершин, смежных с вершиной . Но эта избыточность часто бывает полезна с точки зрения времени выполнения операций над окрестностями вершин графа. Как недостаток такого представления графа, можно отметить неудобство при динамической модификации графа, например, добавление к графу ребра может потребовать большого количества пересылок в массиве . Этого недостатка лишен способ представления графа, показанный на рис. 2.7.




Начало  Назад  Вперед



Книжный магазин