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

0

Как АТД граф представляет собой позиционный контейнер элементов, хранящихся в узлах и путях графа, которые и являются позициями. Следовательно, элементы графа можно хранить либо в узлах, либо в путях, либо и там и там одновременно. С точки зрения реализации на Java это позволяет определить интерфейсы Vertex и Edge, каждый из которых расширяет интерфейс Position. Напомним, что позиция содержит метод element(), возвращающий хранимый в ней элемент.. Будем также использовать специализированные итераторы для узлов и путей, которые называются Vertoxlterator и Edgelterator.

Поскольку граф является позиционным контейнером (см. п. 6.1.3), то АТД «граф» поддерживает методы size(),*isEmpty(), elementsQ, positions(), replace Element^, о) и swapElements(/?,#), где p и q обозначают позиции, а о — объект (то есть элемент).

Графы представляют собой более сложные и насыщенные абстрактные типы данных по сравнению с ранее рассмотренными. Это объясняется

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

Общие методы

Начнем с описания основополагающих методов графов, не учитывающих направление путей. Каждый из перечисленных ниже методов возвращает глобальную информацию о графе G:

numVertices(): возвращает количество узлов в G; numEdges(): возвращает количество путей в G;

vertices(): возвращает итератор узлов G; edges(): возвращает итератор путей G.

В отличие от дерева (имеющего корень), граф не имеет особых узлов. Следовательно, имеется метод, возвращающий произвольный узел в G:

aVertex(): возвращает узел из G.

Далее следуют методы доступа, которые принимают позиции узлов и путей в качестве аргументов:,

degree(v): возвращает степень v;

adjacentVertices(v): возвращает итератор смежного с v узла; incidentEdges(v): возвращает итератор инцидентного для v пути;

endVeirtices(e): возвращает массив размером 2, хранящий конечные точки пути е\

opposite(v,e): возвращает конечную точку пути е, отличную от v;

areAdjacent(v,w): возвращает признак смежности v и w.

Методы работы с направленными путями

Если в графе появляются направленные пути, следует добавить в АТД и несколько дополнительных методов. Начнем с методов работы исключительно с направленными путями.                                                     ^,, ,, ,,

directedEdges(); возвращает итератор всех направленных путей;

undirectedEdgesQ: возвращает итератор всех ненаправленных путей;

destinatiori(e): возвращает точку назначения направленного пути е\

origin(e): возвращает место происхождения направленного пути е\

isDirected(e): возвращает true, если путь е является направленным.

Кррме того, наличие направленных путей требует наличия способа обращения к узлам и путям с учетом направлений.

1

inDegree(v): возвращает полустепень захода v;

outDegree(v): возвращает полустепень исхода v;

inlnCidentEdges(v); возвращает итератор всех входящих в v путей;

outlncidentEdges(v): возвращает итератор всех исходящих из v пу|гей;

inAdjacentVertices(v): возвращает итератор всех узлов, объединенных с v входящими путями;     *

outAdjacentVertices(v): йозвращает итератор всех узлов, объединенных с v

исходящими путями. ,

Методы обновления графа

Ничто не запрещает использовать методы обновления графа для добавления или удаления путей и узлов.

insertEdge(v,w,o): вводит и возвращает ненаправленный путь между узлами v и w, сохраняя объект о в его позиции;

insertDirectedEdge(v,w,o): вводит и возрращает направленный путь между

узлами v и w, сохраняя объект о в его позиции;

insertVeitex(o): вводит ц возвращает новый (изолированный) узел, сохраняя объект о в его позиции;

remove Vertex(o): удаляет узел v и все его инцидентные пути;

removeEdge(e): удаляет путЬ е;

makeUntiirected(e): делает путь е ненаправленным;

reyerseDirection(e): перенаправляет Путь е в обратную сторону;

setDirectionFrom(e,v): делает путь е направленным из узла v;

setDirectionTo(e,v): делает путь е направленным в узел v.

Естественно, такого количества методов для АТД «граф», вполне достаточно. Этр связано в осцрвном,с многообразной структурой графов. При работе нужны методы для разных видов позиций и разных направлений путей, а также методы, которые будут работать с отношениями, устанавливающимися между различными типами позиций.

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

По теме:

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