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

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

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

Задача состоит в том, чтобы перенумеровать все вершины графа таким образом, чтобы любая дуга вела из вершины с меньшим номером в вершину с большим номером. Если граф представляет собой схему выполнения работ, то можно сказать, что такая нумерация задает возможную линейную последовательность работ, например, для последовательного выполнения всех работ одним и тем же работником.
Несложно доказать, что для ориентированного графа без циклов задача имеет, по крайней мере, одно решение. Одно из возможных решений можно найти с помощью следующего алгоритма.
Будем нумеровать вершины, начиная с максимального номера. Дня этого запустим алгоритм обхода в глубину и будем приписывать очередной в порядке убывания номер вершине в тот момент, когда эта вершина окончательно покидается алгоритмом обхода (vertexOut). В этот момент все вершины, достижимые из покидаемой, уже будут пронумерованы и, таким образом, будут иметь номер, заведомо больший номера, приписываемого текущей покидае-
344
Гпава 6
мой вершине. Поскольку граф не имеет циклов, то эта вершина не достижима из нее самой, поэтому все условия задачи оказываются выполненными.
Опишем класс TopSortActor, определяющий посетитель элементов графа, который будет помечать вершины графа в соответствии с правилами топологической сортировки вершин. Маркировка вершины будет осуществляться им при выполнении метода vertexOut. Будем считать, что хранение номеров вершин осуществляется объектом специально описанного класса Marker, который содержит следующие методы:
? setMark(int vertex, int number) — ДЛЯ приписывания номера number вершине vertex;
? getMark(int vertex) — выдающий приписанный вершине vertex номер (-1 — если вершина еще не была пронумерована);
? isMarked(int vertex) — проверяющий, приписан ли вершине некоторый
Разумеется, реализация этих методов не представляет никакого труда. Тогда решение задачи топологической сортировки вершин графа может быть записано так, как показано в листинге 6.4.
Листинг 6.4. Топологическая сортировка вершин графа
// Классы Marker и TopSortActor используются для топологической // сортировки вершин графа, при этом класс Marker определяет // объект для хранения пометок вершин графа, а класс TopSortActor // определяет поведение посетителя вершин графа при выполнении // топологической сортировки.
номер.
//
//-
topsort.h
/h
class Marker { int nVertex; int * marks;
// Общее количество вершин графа // Массив меток вершин
class TopSortActor : public GraphActor {
Marker * marker; // объект для хранения меток вершин
int nextMark; // номер очередной метки при обходе
public :
// Конструктор получает в качестве параметра указатель на // объект, в котором будут храниться метки вершин TopSortActor(Marker * marker);
Алгоритмы обработки графов
345
// Пометка вершины происходит при окончательном // уходе из вершины в процессе обхода; void vertexOut(int vertex);
};
public :
// Конструктор получает ссылку на граф, помечает его вершины // меткой -1, а затем обходит вершины графа с помощью // специально спроектированного посетителя вершин Marker(ListGraph & graph)
: nVertex(graph.vertexCount()), marks(new int[nVertex]), error(false)
{
// 1. Пометка вершин значением -1
for (int i = 0; i < nVertex; i++) marks[i] = -1;
// 2. Обход в глубину с топологической сортировкой вершин TopSortActor actor(this); graph.traverseDepth(actor);
}
// Деструктор уничтожает массив меток вершин ^Marker() { delete marks; }
// Число вершин в массиве
int vertexCount() const { return nVertex; }
H Функция для проверки, помечена ли вершина
bool isMarked(int vertex) const { return marks[vertex] != -1; }
// Функция выдачи метки вершины
int getMark(int vertex) const { return marks[vertex]; }
};
//-------- topsort.cpp --------------------------------------------------------
// В конструкторе посетителя вершин первая метка // получает значение, равное количеству вершин графа.
Marker::TopSortActor::TopSortActor(Marker * marker)
: marker(marker), nextMark(marker->vertexCount()) {}
// При пометке вершины текущее значение метки уменьшается на единицу void Marker::TopSortActor::vertexOut(int vertex) { marker->marks[vertex] = —nextMark;
}
346
Гпава 6
Если применить эту процедуру к графу, изображенному на рис. 6.3, то получится маркировка вершин, показанная ниже:
Vertex # 0 has a mark # 2
Vertex # 1 has a mark # 4
Vertex # 2 has a mark # 0
Vertex # 3 has a mark # 5
Vertex # 4 has a mark # 1
Vertex # 5 has a mark # 3
С помощью того же самого алгоритма можно проверить, действительно ли граф не имеет циклов. Для этого достаточно при прохождении дуги (arcForward) проверять, не ведет ли эта дуга в уже пройденную, но еще не пронумерованную вершину. Расширенный алгоритм топологической сортировки будет выдавать ошибку, если исходный граф содержит цикл, а в противном случае маркировка вершин будет проведена до конца без ошибок. Такое расширение алгоритма реализовано в программе, содержащейся на приложенном компакт-диске В папке "Chapter6\6.1\GraphIterators".
Предыдущая << 1 .. 114 115 116 117 118 119 < 120 > 121 122 123 124 125 126 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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