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

0

Существует несколько способов реализации АТД «граф» с помощью конкретных структур данных. Рассмотрим три наиболее известных: список путей (edge list structure), список смежности (adjacency list structure) и матрицу смежности (adjacency matrix). В каждой из них используется контейнер (список или вектор) для хранения узлов графа. Хранение же путей между первыми двумя и последней структурами значительно различается. Структура списка путей и структура списка смежности хранят только пути, непосредственно имеющиеся в графе, в то время как матрица смежности сохраняет заглушки для каждой пары узлов (независимо от того, соединены они путем или нет). Это различие предполагает, что для графа G из п узлов и т путей список путей или список смежностй будут занимать 0(п + т) места, а матрица требует 0(п2) места.

Структура списка путей

Структура списка путей представляется наиболее простой, хотя и не самой эффективной формой представления графа G. В этой структуре узел vb G, хранящий элемент о, явно выражен узловым объектом. Все такие объекты узлов хранятся в крнтейнере К, обычно представленном списком, вектором или словарем. При работе с вектором все объекты в нем, естественно, должны быть пронумерованы. В словаре каждый узел должен иметь ассоциируемый с ним ключ. К тому же словарю желательно поддерживать локаторнук) модель (см. раздел 8.7). Заметим, что элементами контейнера V являются позиции узлов графа G.

Объект узла

Объект узла для хранения элемента о имеет следующие переменные экземпляра:

[1]        для ссылки на о,

•      счетчиков количества инцидентных ненаправленных путей, входящих направленных путей и исходящих направленных путей,

•               ссылки на позиции^ (или локатор) узла-объекта в контейнере V.

Однако отличительной характеристикой структуры списка путей является не способ представления узлов, а способ представления путей. Путь е в G, хранящий элемент о, также явно представлен объектом пути. Этот объект хранится в контейнере Е, который может быть представлен списком, вектором или словарем (возможно, поддерживающим локатор- ную модель).

Объект пути

Объект «путь» для представления пути, хранящего элемент о, имеет следующие переменные экземпляра:

•   для ссылки на о,                                                         \

•    булева индикатора типа пути е (направленный или ненаправленный),

•      ссылок на узловые объекты в V, ассоциируемые с конечными точками пути е (есди е ненаправленный) или точки происхождения и назначения (если е — направленный путь),

•    ссылки на позицию (или локатор) пути-объекта в контейнере Е.

Схематическое представление структуры списка путей направленного графа представлено на рис. 12.3.

Список путей

Причина названия этой структуры списком путей ясна, поскольку наиболее распространенной реализацией контейнера ? является список. Но даже в этом случае, чтобы обеспечить возможность удобного поиска объекта, ассоциируемого с путем, может понадобиться реализовать Е с помощью словаря, несмотря на название «список». По той же причине и контейнер К может реализоваться в виде словаря. Но название структуры при этом не изменится.

Главная характеристика структуры списка путей — это возможность прямого доступа из йутей в узлы, для которых они являются инцидентными, что позволяет использовать простые алгоритмы реализации различных методов работы с АТД «граф», основывающихся на путях (как, например, endVertices, origin или destination). Чтобы реализовать каждый из этих методов, следует просто обратиться к соответствующему компоненту данного объекта пути.

Рис. 12.3. (а) Направленный граф; (Ь) схематическое представление структуры списка путей для G. Чтобы не загромождать рисунок, не показаны следующие поля объектов узлов: три счетчика инцидентных путей и ссылки на позицию (или локатор) узла-объекта в контейнере К Также не показаны следующие поля объектов путей: булев индикатор направления и ссылка на позицию (или локатор) пути-объекта в контейнере Е. И наконец, с помощью имен вместо ссылок на их объекты представлены элементы, хранящиеся в объекте узла и пути

(Ь)

Но, несмотря на это, «обратная» операция, используемая для доступа к инцидентным путям узла, требует тщательной проверки всех объектов путей контейнера Е, то есть, чтобы определить инцидентный для данного узла v путь, требуется проверить все пути списка. Тогда метод incidentEdges_(v), например, выполняется за время, пропорциональное количеству узлов в графе, а не за время, пропорциональное степени узла v. На самом деле даже для проверки с помощью метода areAdjacent(v,w) смежности двух узлов v ww необходимо просмотреть весь список, чтобы найти путь (v,w) или (w,v). Более того, поскольку удаление узла включает в себя удаление всех проходящих через него путей, метод remove Vertex тоже требует поиска по всему списку путей Е.

(а)

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

t, Ни^ке приведены показатели производительности реализации списка путей графа.

Операция

Время

size, isEmpty, replaceElement, swapElements

0(1)

numVertices, numEdges, aVertex

0(1)

vertices

0(ri)

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, areAdjacent

0(m)

insertVertex, insertEdge, insertDirectedEdge, removeEdge,

 

makellndirected, reverseDirection, setDirectionFrpm, setDirectionTo

0(1)

removeVertex

0(m)

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

Описания отдельных методов АТД «граф»:

[1]       методы numVertice$(), numEdges() и size() выполняются за 0(1) времени, возвращая \Z.size(), E.size() и \Z.size() + E.sizeQ соответственно;

•             счетчики, хранящиеся с каждым объектом узла, позволяют выполнять методьг^едгеё, inDegree n’outDegtee за время, пропорциональное 0(1);

•             методы vertices() и edges() реализуются вызовом \/.elements() и E.elements() соответствённо; ‘

•             итераторы directEdges() и undirectEdg6s() реализован^ вызовом Eele- ments()?n возвращают пути; соответствующие указанному типу;

•             поскольку контейнеры Vи Е явлйютсй списками, реализованными двусвязными списками, ввод узла, ввод и удаление пути осуществт ляются за 0(1) времени;

•             методы incidentEdges, inlncidentEdg^s, outlncident?dges, adjacent- Vertices, inAdjacentVertices и areAdjacent требуют 0(m) времени каждый, так как определяют инцидентные для данного узла v пути;

•             метод обновления removeVertex{ V) выполняется за 0{т) времени, поскольку нам нужно исследовать все связи для поиска и удаления проходящих.ч^ерез узед^Кпутей.   . , • ;.

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

По теме:

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