Компьютерные книги
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 118

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 112 113 114 115 116 117 < 118 > 119 120 121 122 123 124 .. 161 >> Следующая

ListGraph::ExtGraphlterator * iter -
new ListGraph::ExtGraphlterator(StestGraph) while (iter->hasMoreElements()) { cout « **iter « ' ;f;
++*iter;
}
cout « endl « iter->getComponentsPassed()
« " components passed" « endl; delete iter;
return 0;
При обходе вершин (и дуг) графа часто приходится выполнять более сложную работу, чем элементарная нумерация вершин или подсчет числа компонент связности. В Зтой ситуации более гибким оказывается аппарат применения внутренних итераторов. При этом структура графа вне определения класса, реализующего граф, обычно неизвестна. Поэтому техника, при которой посетитель узла сам определяет порядок и содержание дальнейших посещений, оказывается неприменимой. Более удобным и часто используемым решением будет определение внутреннего итератора, который обходит узлы и дуги графа по заданному им самим алгоритму, вызывая при этом различные функции при заходе в узлы, при выходе из узлов, при прохождении по дуге и т. п.
Определим, например, обход в глубину в виде внутреннего итератора, который получает объект-посетитель в качестве аргумента и вызывает различные методы этого посетителя во время прохождения вершин и дуг графа. Во время обхода в глубину для каждой вершины графа есть два существенных момента времени. Первый — это момент, когда вершина посещается в первый раз. Именно в этот момент наш внешний итератор ExtGraphlterator выдавал номер этой вершины в качестве очередной (в реализации метода operator ++ переменная current в этот момент получала новое значение). Второй существенный момент— это момент окончательного покидания вершины, когда уже рассмотрены все выходящие из нее дуги. Это тот момент, когда происходит возврат по дуге, ведущей в эту вершину, а для вершины, выбранной
338
Глава 6
в качестве начальной, — это момент, когда заканчивается рассмотрение одной компоненты связности.
Для каждой дуги также можно выделить два основных момента: момент, когда происходит переход по этой дуге в новую или в уже посещенную ранее вершину, и момент, когда происходит возврат по этой дуге. Если дуга ведет в уже посещенную ранее вершину, то возврат происходит сразу же. Если же дуга ведет в новую вершину, то возврат по этой дуге произойдет только после того, как эта вершина будет покинута окончательно.
Существенным моментом при обходе в глубину является также момент выбора произвольной вершины, когда уже исследованы все пути, ведущие из ранее выбранной вершины. Для неориентированного графа это соответствует моменту перехода к новой компоненте связности графа. Соответствующий этому моменту метод также следует включить в интерфейс работы посетителя.
Итак, определим интерфейс посетителя узлов и дуг графа таким образом, чтобы в нем содержались методы для обработки вершин на входе и выходе, для обработки дуг на пути туда и обратно, а также для обработки момента выбора очередной вершины при переходе к новой компоненте связности графа. Методы обработки вершин получат в качестве аргумента номер обрабатываемой вершины, а методы обработки дуг получат в качестве аргументов номера вершин, которые эта дуга соединяет, и информацию о том, посещалась ли ранее та вершина, в которую ведет эта дуга. Вот как может выглядеть определение такого интерфейса:
class GraphActor { public :
virtual void vertexln(int vertex) {} virtual void vertexOut(int vertex) {}
virtual void arcForward(int begin, int end, bool newVertex) {} virtual void arcBackward(int begin, int end) {} virtual void newSelection(int vertex) {}
};
Методы интерфейса GraphActor определены не как чистые функции, а как пустые функции — функции, не совершающие никаких действий. Это позволит при определении реальных посетителей задавать лишь необходимую часть действий по обработке элементов графа, оставляя без внимания несущественные для данной конкретной задачи моменты обхода.
Сам обход вершин и дуг графа может быть реализован по тому же самому алгоритму, который был использован нами для реализации внешнего итератора. В листинге 6.3 такая реализация приведена в виде метода traverseDepth () класса ListGraph. Несколько изменена структура объектов, помещаемых в
Алгоритмы обработки графов
339
стек дуг. В представлении Z-графа дуга содержит информацию только о номере вершины, в которую она входит. Однако при прохождении дуги требуется знать также и вершину, из которой дуга исходит. Поэтому в стек помимо итератора элементов списка дуг помещается также номер исходящей вершины для обрабатываемого списка дуг. Структура Pair представляет тип элементов стека — пару из номера вершины и указателя на итератор элементов списка дуг.
j Листинг 6.3. Обход в глубину с помощью внутреннего итератора
class ListGraph { public:
// Обход графа с помощью внутреннего итератора void traverseDepth(GraphActor & actor);
protected :
// Пара из номера вершины и итератора исходящих дуг // определяется для работы внутреннего итератора struct Pair {
int sourceVertex;
Iterator<int>* iterator;
Pair(int v = -1, Iterator<int>* i = NULL)
: sourceVertex(v), iterator(i) {}
Предыдущая << 1 .. 112 113 114 115 116 117 < 118 > 119 120 121 122 123 124 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Завалишин Д. "Интернетско-русский разговорник" (Web-программирование)

Заенцев И.В. "Нейронные сети: основные модели" (Web-программирование)

Владимиров А.А. "Wi-фу: «боевые» приемы взлома и защиты беспроводных сетей" (Web-программирование)

Вьейра Р. "SQL Server 2000. Программирование в 2 ч." (Web-программирование)

Веллинг Л.Т. "Разработка web приложений с помощью php и mysql" (Web-программирование)
Авторские права © 2013 ComputersBooks. Все права защищены.

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed