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

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

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

};
};
void ListGraph::traverseDepth(GraphActor & actor) {
// множество непройденных вершин:
Set setNotPassed(0, vertexCount()-1); setNotPassed.addScale(0, vertexCount()-1);
// стек дуг:
ListStack<Pair> arcs;
// Цикл по компонентам связности графа while (!setNotPassed.empty()) {
// Выбираем произвольную вершину из еще не пройденных Iterator<int> * setlterator = setNotPassed.iterator(); int current = **setIterator;
// Отмечаем заход в новую компоненту связности actor.newSelection(current); delete setlterator;
// Список неисследованных дуг, исходящих из очередной вершины Iterator<int> * curList = graph[current].iterator();
340
Гпава 6
II Цикл по вершинам одной компоненты связности while (current != -1) {
// Проходим текущую вершину setNotPassed -= current; actor.vertexln(current);
// Цикл прохода по дугам for (;;) {
// Есть дуга, ведущая из текущей вершины? if (curList->hasMoreElements()) { int arcEnd = **curList;
bool newVertex = setNotPassed.has(arcEnd);
++*curList;
// Проходим вперед по выбранной дуге
actor.arcForward(current, arcEnd, newVertex);
if (newVertex) {
// Дуга ведет в новую ранее не рассмотренную вершину.
// Запоминаем ситуацию, делаем шаг вперед по выбранной дуге //и переходим к рассмотрению следующей вершины arcs.push(Pair(current, curList)); current = arcEnd;
curList = graph[current].iterator(); break;
} else {
// Дуга ведет в уже пройденную вершину.
// Выполняем обратный проход по этой дуге actor.arcBackward(current, arcEnd);
}
} else {
// Покидаем окончательно текущую вершину и // возвращаемся к предыдущим вершинам actor.vertexOut(current); delete curList; if (arcs.empty()) {
// Компонента связности пройдена полностью
current = -1;
break;
} else {
// Делаем обратный проход по дуге, извлеченной из стека дуг Pair previous = *arcs; arcs.pop();
actor.arcBackward(previous.sourceVertex, current); current = previous.sourceVertex;
Алгоритмы обработки графов
341
curList = previous.iterator;
}
}
}
}
}
}
Полный протокол работы итератора можно посмотреть, если определить посетителя, который будет протоколировать все заявленные действия. Ниже представлено описание такого класса Logger и приведен пример вызова функции обхода графа с помощью такого посетителя.
class Logger : public GraphActor { public :
void vertexln (mt vertex) {
cout « "In vertex: " « vertex « endl;
}
void vertexOut(int vertex) {
cout « "Out vertex: " « vertex « endl;
}
void arcForward(int begin, int end, bool newVertex) { cout « "Arc forward (" « (newVertex ? "new" : "old")
« "): (" « begin « "-" « end « ")" « endl;
}
void arcBackward(int begin, int end) {
cout « "Arc backward: (" « begin « "-" « end « ")" « endl;
}
void newSelection(int vertex) {
cout « "New component started from vertex: " « vertex « endl;
}
} logger;
testGraph.traverseDepth(logger);
Для приведенного на рис. 6.1 примера в результате работы итератора будет выведен следующий протокол:
New component started from vertex: 0 In vertex: 0
Arc forward (new): (0-1)
In vertex: 1
Arc forward (new): (1-4)
In vertex: 4
342
Гпава 6
Arc forward (new): (4-6)
In vertex: 6
Arc forward (new): (6-3)
In vertex: 3
Arc forward (old): (3-0)
Arc backward: (3-0)
Out vertex: 3 Arc backward: (6-3)
Out vertex: 6 Arc backward: (4-6)
Arc forward (new): (4-7)
In vertex: 7
Out vertex: 7
Arc backward: (4-7)
Out vertex: 4 Arc backward: (1-4)
Arc forward (old): (1-7)
Arc backward: (1-7)
Out vertex: 1 Arc backward: (0-1)
Arc forward (old): (0-4)
Arc backward: (0-4)
Arc forward (old): (0-6)
Arc backward: (0-6)
Out vertex: 0
New component started from vertex: 2 In vertex: 2
Arc forward (new): (2-8)
In vertex: 8
Arc forward (new): (8-5)
In vertex: 5
Arc forward (old): (5-2)
Arc backward: (5-2)
Out vertex: 5 Arc backward: (8-5)
Out vertex: 8 Arc backward: (2-8)
Out vertex: 2
Задача о переборе всех компонент связности неориентированного графа будет теперь решаться с помощью подходящего определения посетителя дуг и вершин графа. Для этого определим класс component Logger, реализующий интерфейс GraphActor. Этот посетитель должен будет при выборе очередной
Алгоритмы обработки графов
343
вершины (newSelection) выдавать информацию о начале новой компоненты связности, а при заходе в каждую новую вершину печатать ее номер. Ниже показан соответствующий фрагмент программы.
class ComponentLogger : public GraphActor { int compNumber; public :
ComponentLogger() : compNumber(0) {}
void vertexln(int vertex) { cout « vertex « "; "; } void newSelection(int vertex) {
cout « endl « "Component #: " « ++compNumber « endl;
}
} compLogger;
testGraph.traverseDepth(compLogger);
С помощью внутреннего итератора, определенного таким образом, можно решать и более сложные задачи. Например, -следующая задача известна под названием топологической сортировки вершин графа.
Пусть ориентированный граф не имеет циклов, т. е., если, следуя по направлению дуг, можно попасть из вершины А в вершину 5, то из вершины В попасть в вершину А заведомо невозможно. В частности, это означает, что в графе нет петель — дуг вида (А, А). Примером такого графа может служить схема выполнения некоторого множества работ, причем элементарные работы обозначаются вершинами графа, а дуга проводится из вершины А в вершину В, если работа В может быть выполнена только после того, как закончится выполнение работы^.
Предыдущая << 1 .. 113 114 115 116 117 118 < 119 > 120 121 122 123 124 125 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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