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

0

Как и в случае со списком смежности, матрица смежности расширяет структуру списка путей с помощью дополнительных компонентов. В данном случае в список путей добавляется матрица (двухмерный массив) А, что позволяет определять смежности пар узлов за пропорциональный 0(1) промежуток времени. Как будет показано далее, такое повышение скорости требует значительных объемов памяти.

В матричном представлении рассматриваем узлы как целые числа множества {0,1,…, п – 1}, а пути — как пары этих целых чисел. Это позволяет сохранять ссылки на пути в ячейках двухмерного массива А размером пх п. В частности, матрица смежности расширяет структуру списка путей следующим образом:

•              объект узла v хранит уникальный целочисленный ключ, называе-

•      мый индексом узла v, в пределах 0, 1, …, п – 1. Для простоты будем ссылаться на узел с индексом / как на «узел /»;

•      двухмерный массив А размером п х п организуем таким образом, что ячейка А[i,J\ содержит ссылку на объект пути е, идущего из узла с индексом / в узел с индексом у, если такой путь существует. Если путь е, соединяющий узлы / и у, ненаправленный, то ссылка на е хранится в А[/,у] и А[у, /] одновременно. Если такой путь между узлами i и у отсутствует, то А[/,у] ссылается на нулевой объект (или другой индикатор, показывающий, что ячейка не соответствует ни одному из путей).

Матрица смежности А позволяет выполнять метод areAdjacent(v,w) за 0(1) времени. Такая производительность достигается за счет обращения к узлам v и w для определения соответствующих им индексов / и у и проверки наличия ссылки из ячейки А[/,у] на нулевой объект. Однако такое повышение производительности достигается за счет увеличения как используемого пространства, составляющего теперь 0(п2), так и времени выполнения других методов. Например, методы узлов incidentEdges, adjacentVertices, inAdjacentVertices и outAdjacentVertices потребуют прохождения всего ряда или столбца массива А, что займет 0(п) времени. Более того, ввод или удаление узла также требуют создания нового массива увеличенного (уменьшенного) размера соответственно, что займет 0{п2) времени.

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

В табл. 12.3 сведены показатели производительности графа, реализованного в виде матрицы смежности. Из таблицы следует, что такая реализация уступает структуре списка смежности по занимаемому пространству и скорости выполнения методов, за исключением метода areAdjacent.

(C)

Рис. 12.5. Схематическое отображение структуры матрицы смежности: (а) направленный граф G\ (b) нумерация узлов в G\ (с) матрица смежности А для графа G


Операция

Время

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, inlncidentEdges, outlncidentEdges, adjacentVertices, inAdjacentVertices, outAdjacentVertices

0(n)

areAdjacent

0(1)

insertVertex, insertEdge, insertDirectedEdge, removeEdge, makellndirected, reverseDirection, setDirectionFrom, setDirectionTo

0(1)

insertVertex, rempveVertex

0(и2)

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

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

Большинство рассматриваемых в этой книге алгоритмов работает эффективнее в графах, представленных в виде списков смежности. Однако на практике встречаются случаи, когда графы с небольшим количеством путей быстрее обрабатываются списком смежности, а графы с большим количеством путей — матричной структурой.

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

По теме:

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