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

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

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

334
Гпава 6
// Функция подсчета числа вершин просто выдает // ранее сохраненное значение
int vertexCount() const { return vertexNumber; }
// Основные методы работы с графом void addArc (int from, int to); bool hasArc(int from, int to) const;
Iterator<int> * iterator() { return new ExtGraphlterator(this); }
};
/ / ====-===-=========================:==========================
// Методы класса ListGraph //=^==========================================================:==:==========:==
// Добавление дуги
void ListGraph::addArc(int from, int to) {
if (from <0|| from >= vertexNumber I| to < 0 || to >= vertexNumber) return; // Неправильно задана дуга
graph[from].addLast(to);
}
// Поиск дуги
bool ListGraph: :hasArc (int from, int to) const {
if (from < 0 || from >= vertexNumber || to < 0 |I to >= vertexNumber) return false; // Неправильно задана дуга
// Перебираем все дуги с помощью итератора элементов списка Iterator<int> * ends = graph[from].iterator(); bool found = false;
while (ends->hasMoreElements() && !(found = (to == **ends))) ++*ends; delete ends; return found;
}
//======================—======================—=============
// Методы итератора вершин графа //=============================:==================
// Конструктор внешнего итератора вершин графа
ListGraph::ExtGraphlterator::ExtGraphlterator(ListGraph *graph) :
// множество непройденных вершин: setNotPassed(0, graph->vertexCount()-1),
// текущая вершина - произвольно берем нулевую вершину: current(0),
Алгоритмы обработки графов
335
II стек непросмотренных дуг:
arcs(new ListStack<Iterator<int>*>),
11 граф, подлежащий обходу: graph(graph)
{
//В множество непройденных вершин помещаются все вершины графа setNotPassed.addScale(0, graph->veгtexCount()-1);
}
// Функция, устанавливающая в качестве текущей // следующую вершину на пути обхода графа в глубину Iterator<int> & ListGraph::ExtGraphlterator::operator ++() {
// 1. Проверка корректности вызова if (!hasMoreElements()) return *this;
// 2. Проходим текущую вершину, удаляя ее из списка непройденных setNotPassed -= current;
// 3. Находим очередную вершину. При этом сначала // рассматриваем дуги, выходящие из текущей вершины Iterator<int> *nextPoints = (graph->graph)[current].iterator(); for (;;) {
if (!nextPoints->hasMoreElements()) {
// Очередной дуги нет delete nextPoints; if (arcs->empty()) {
// стек дуг также пуст: компонента связности пройдена,
// выбираем следующую из множества непройденных вершин //и переходим тем самым к следующей компоненте связности Iterator<int> * setlterator = setNotPassed.iterator(); current = (setIterator->hasMoreElements() ? **setIterator : -1); delete setlterator; return *this;
} else {
// выбираем очередную дугу из стека nextPoints = **arcs; arcs->pop();
}
}
// Дуга, ведущая в некоторую вершину, найдена
int vertex = *^nextPoints; II это будет следующая вершина
++*nextPoints;
if (setNotPassed.has(vertex)) {
336
Гпава 6
II это непройденная вершина; она объявляется текущей current = vertex;
if (nextPoints->hasMoreElements()) {
// если есть еще дуги, ведущие из этой вершины,
// то итератор множества вершин записывается в стек arcs->push(nextPoints);
} else {
delete nextPoints;
}
return *this;
Обход в глубину оказывается полезным в случае неориентированного графа (напомним, что в представлении неориентированного графа вместе с любой дугой (А, В) обязательно содержится и дуга (В, А)). В этом случае, какую бы вершину ни взять в качестве исходной, в качестве следующих будут выбраны все достижимые из нее вершины. Таким образом, все вершины, принадлежащие одной и той же компоненте связности, получают последовательные порядковые номера.
Момент перехода от одной компоненты связности к другой в алгоритме перебора вершин отмечен в функции комментарием. Если добавить в итератор счетчик компонент связности и увеличивать его при каждом переходе к новой компоненте, то мы сможем легко получить функцию, которая будет выдавать количество пройденных компонент связности. В листинге 6.2 приведен пример, в котором создается неориентированный граф, полученный из графа рис. 6.1 добавлением всех обратных дуг, а затем его вершины последовательно обходятся в глубину. В конце работы выдается количество пройденных компонент связности графа (предполагается, что соответствующая функция getComponentsPassedO уже определена В классе ExtGraphlterator).
Листинг 6.2. Перечисление вершин графа по компонентам связности
int main() {
ListGraph testGraph(9) testGraph.addArc(0, 1) testGraph.addArc(0, 4) testGraph.addArc(0, 6) testGraph.addArc(1, 4) testGraph.addArc(1, 7) testGraph.addArc(2, 8)
testGraph.addArc(1, 0) testGraph.addArc(4, 0) testGraph.addArc(6, 0) testGraph.addArc(4, 1) testGraph.addArc(7, 1) testGraph.addArc(8, 2)
Алгоритмы обработки графов
337
testGraph.addArc(3, 0) testGraph.addArc(4, б) testGraph.addArc(4, 7) testGraph.addArc(5, 2) testGraph.addArc(6, 3) testGraph.addArc(8, 5)
testGraph.addArc(0, 3) testGraph.addArc(6, 4) testGraph.addArc(7, 4) testGraph.addArc(2, 5) testGraph.addArc(3, 6) testGraph.addArc(5, 8)
Предыдущая << 1 .. 111 112 113 114 115 116 < 117 > 118 119 120 121 122 123 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Завалишин Д. "Интернетско-русский разговорник" (Web-программирование)

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

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

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

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed