Главная » Java, Структуры данных и алгоритмы » Структура списка смежности

0

для. графа G расширяет структуру списка путей, добавляя сведения, которые поддерживают прямой доступ к инцидентным путям (и, таким образом, к объединенным узлам) каждого узла. В то время как список путей рассматривает отношение уЗла и инцидентного пути со стороны последнего, структура списка смежности позволяет рассмотреть это отношение с обеих сторон. Такой симметричный подход позволяет реализовывйть методы работы с узлами АТД «граф» с помощью списка смежности гораздо быстрее, хотя обе структуры списка смежности используют пространство, пропорциональное количеству узлов и путей в графе. включает в себя все структурные компоненты списка путей и дополнительно включает следующее:

•      объект узла v содержит ссылку на контейнер I(v) инцидентных Путей узла (incident container), содержащий ссылки на них. Если граф включает и направленные пути, то контейнер разбивается на три контейнера Iin(v), Iout(v) й Iun(v) для хранения входящих, исходящих и ненаправленных путей соответственно;

•      объект пути (u,v) содержит ссылки на его позиции (или локаторы) в контейнерах 1(и) и /(v).

Список смежности

Традиционно контейнер инцидентных путей /(v) для узла реализуется списком (откуда и название списка смежности). Но и здесь возможно представление контейнера инцидентных путей словарем или приоритетной очередью. Так что будем считать, что /(v) является универсальным контейнером для объектов путей. Если требуется, чтобы представление поддерживало граф G, потенциально способный содержать как направленные, так и Ненаправленные пути, то применяем три контейнера //„(v), Iout(v) и 1ип(У) Для хранения ссылок на соответствующие типы путей.

обеспечивает прямой доступ из Путей в узлы, и наоборот — из узлов в их инцидентные пути. Эта возможность списка смежности позволяет значительно повысить скорость выполнения методов графа по сравнению со списком путей. На рис. 12.4 приведена структура списка смежности. Занимаемое под контейнер инцидентных путей пространство пропорционально степени узла, то есть равно 0(deg(v)). Таким образом, согласно утверждению 12.6, структура списка смежности занимает 0(п + т) пространства.

Производительность

В табл. 12.2 приводятся сводные данные производительности графа, представленного списком смежности, исходя из того, что V, Е и инцидентные структуры реализованы связными списками.

(a)

(b)

Рис. 12.4. (а) Направленный граф G\ (b) схематическое представление структуры списка смежности для G. Как и на рис. 12.3, не приводятся некоторые поля объектов узлов и путей, а элементы контейнера представлены именами вместо объектов. Также показан только контейнер для направленных путей, так как в этом графе нет ненаправленных путей

Подчеркнем, что все методы графического АТД могут быть реализованы такой структурой за 0(1) времени (как в списке путей) с помощью практически тех же алгоритмов. Кроме того, структура списка смежности рбеспечивает меньшее время выполнения для следующих методов:

•      методы, возвращающие итераторы инцидентных путей или объединенных узлов для узла v, могут выполняться за время, пропорциональное размеру итераторов, то есть за 0(deg(v));

•      метод areAdjacent(w,v) может выполняться поиском либо в контейнере иь либо в контейнере v. Для меньшего из двух контейнеров инцидентных путей получим время выполения 0(min(deg(w),deg(v));

•      метод removeVertex(v) требует проверки контейнера инцидентных путей узла v, и, таким образом, необходимо 0(deg(v)) времени.

Операция

Время

size, isEmpty, replaceElement, swapElements

0(1)

numVertices, numEdges, aVertex

0(1)

vertices

0(n)

edges, directedEdges, undirectedEdges

0(m) ‘

elements, positions

0(n+m)

endVertices, opposite, origin, destination, isDirected, degree,

 

inDegree, outDegree

0(1)

incidentEdges(v), inlncidentEdges(v), outlncidentEdges(v),

 

adjacentVertices(\/), inAdjacentVertices(\/), outAdjacentVertices(\/)

0( deg(v))

areAdjacent(u, \/)

0(min(deg(M), deg(v))

insertVertex, InsertEdge, insertDirectedEdge, removeEdge,

 

makellndirected, reverseDirection, setDirectionFrom,

 

setDirectionTo

0(1)

remove Vertex(y)

0(deg(v))

Таблица 12.2. Время выполнбния методов графа, реализованного структурой списка смежности так, что контейнеры V и Е и их контейнеры инцидентных путей реализованы с помощью списков, в свою очередь реализованных двусвязными списками. Количество узлов обозначено п, а количество путей — т. Занимаемое пространство равно 0(п + т)

Преимуществом структуры списка смежности по сравнению со струк-г турой списка путей является возможность выполнения методов построения итераторов узла за 0(deg(v)) времени, в отличие от О(т) в списке путей. Более того, метод areAdjacent(w,v) может быть усовершенствован, если воспользоваться для реализации контейнера Е быстрым словарем, ключами которого будут пары узлов; подробности оставлены для упражнения 3-12.4.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии