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

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

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

// Конструктор // graph - граф для обхода //====================:====================:================,
BreadthGraphlterator(ListGraph *graph); //==============================
// Деструктор
//========================================================,
--BreadthGraphlterator () { delete qNext; }
// Функция проверяет, остались ли еще не пройденные вершины bool hasMoreElements() const {
return !qNext->empty() || !setNotPassed.empty();
}
: public Iterator<int> {
// граф для обхода
// очередь вершин
// множество непройденных вершин
350
Гпава 6
// Функция сдвига итератора на следующую вершину //в порядке обхода вершин графа в глубину Iterator<int> & operator ++();
// Функция, выдающая номер очередной вершины на пути обхода const int & operator *() const { return qNext->head(); }
};
// Создание внешнего итератора вершин графа (обход в ширину) Iterator<int> * breadthlterator() {
return new BreadthGraphlterator(this) ;
}
};
// Методы внешнего итератора вершин графа (обход в ширину)
//**************************************************************
// Конструктор внешнего итератора вершин графа
ListGraph::BreadthGraphlterator::BreadthGraphlterator(ListGraph *graph) : // множество непройденных вершин: setNotPassed (0, graph->vert;exCount () -1) ,
// стек непросмотренных дуг: qNext(new ListQueue<int>),
// граф, подлежащий обходу: graph(graph)
{
//В множество непройденных вершин помещаются все вершины графа setNotPassed.addScale(0, graph->vertexCount()-1);
// Выбираем очередную вершину operator ++();
}
// Функция сдвига итератора на следующую вершину
//в порядке обхода вершин графа в глубину
Iterator<int> & ListGraph::BreadthGraphlterator::operator ++() {
// Сначала проверяем очередь; если она не пуста,
// то надо удалить изчнее очередную вершину и // поставить в очередь ее непройденных потомков if (!qNext->empty()) {
// Выбираем вершину из очереди int vertex = qNext->head(); qNext->dequeue();
// Просматриваем дуги, ведущие из этой вершины Iterator<int> *arcs = (graph->graph)[vertex].iterator();
Алгоритмы обработки графов
351
while (arcs->hasMor&Elements()) { int next = **arcs; if (setNotPassed.has(next)) { qNext->enqueue(next); setNotPassed -= next;
}
++*arcs;
}
}
// Теперь проверяем, есть ли еще непройденные вершины if (!hasMoreElements()) { return *this;
}
// Наконец, если очередь не содержит больше вершин,
//то очередная вершина берется из множества непройденных. if (qNext->empty()) {
// Выбираем произвольную вершину из еще не пройденных Iterator<int> * setlterator = setNotPassed.iterator(); int selected = **setIterator; delete setlterator;
qNext->enqueue(selected); setNotPassed -= selected;
}
return *this;
}
В листинге 6.7 тот же алгоритм приведен в виде внутреннего итератора, представленного методом traverseBreadth С аргументом класса GraphActor. Поскольку при обходах в ширину бессмысленно говорить о возвратах по дуге, то методы arcBackward и vertexOut нигде в этой функции не вызываются. Соответственно, нет смысла переопределять эти методы в наследниках этого класса при использовании обхода в ширину.
||litefHHr6.T.;Bri^e^HH^f^paf<>^ -‘’г;-..
class ListGraph {
// Массив списков дуг List<int> *graph;
// Количество вершин графа int vertexNumber;
352
Гпава 6
public:
// Функция обхода графа в ширину с помощью внутреннего итератора void traverseBreadth(GraphActor & actor);
};
//**************************************************************
// Метод для внутренней итерации вершин графа (обход в ширину) j ^-к-к'к'к-к-к-к-к'к'к'к-к-к'к'к'к'к'к-к'к'к-к'к'к'к'к'к'к'к'к'к-к'к'к'к'к'к'к-к-к'к'к'к'к'к'к'к'к'к'к'к'к'к'к'к-к'к'к'к'к-к'к
void ListGraph::traverseBreadth(GraphActor & actor) {
// Очередь вершин
Queue<int> *qNext = new ListQueue<int>;
// Множество еще не пройденных вершин Set setNotPassed;
setNotPassed.addScale(0, vertexCount()-1);
while (!(qNext->empty() && setNotPassed.empty())) { if (qNext->empty()) {
// Выбор очередной исходной вершины
Iterator<int> * setlterator = setNotPassed.iterator(); int selected = **setIterator; delete setlterator;
// Вершина ставится в очередь qNext actor.newSelection(selected); qNext->enqueue(selected); setNotPassed -= selected;
}
// Выбор вершины из очереди int vertex = qNext->head(); qNext->dequeue();
actor.vertexln(vertex);
// Просмотр всех дуг, ведущих из этой вершины Iterator<int> *iArcs = graph[vertex].iterator(); while (iArcs->hasMoreElements() ) {
int next = **iArcs;
bool newVertex = setNotPassed.has(next); actor.arcForward(vertex, next, newVertex); if (newVertex) {
qNext->enqueue(next); setNotPassed -= next;
}
Алгоритмы обработки графов
353
++*iArcs;
}
delete iArcs;
}
}
Обходы графа в ширину применяются в следующем разделе для поиска кратчайших путей в графе.
6.2. Поиск кратчайших путей
Путем в графе называют чередующуюся последовательность вершин и дуг Vi, eu v2, е2,.-. Vn ь }, v„, в которой каждый элемент v,-— вершина графа, а каждый элемент е, — дуга графа, ведущая из предыдущей вершины v, в следующую вершину V/ f 1. Говорят, что такой путь соединяет вершину v\ с вершиной v„. Чаще всего рассматриваются простые пути, т. е. такие, в которых нет повторяющихся вершин, кроме, быть может, совпадения первой и последней вершины. В случае такого совпадения путь называется замкнутым или циклом.
Предыдущая << 1 .. 116 117 118 119 120 121 < 122 > 123 124 125 126 127 128 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.