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

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

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 10 11 12 13 14 15 < 16 > 17 18 19 20 21 22 .. 161 >> Следующая

Последний пример. Программа игры в шахматы для анализа позиции строит сеть, состоящую из позиций, связанных между собой возможными ходами соперников. Узлы сети могут характеризоваться игровой оценкой позиции, а связывающие позиции ходы могут характеризоваться локальными целями и т. д.
Для моделирования сетей в математике служат объекты, называемые графами. Графом G называется пара множеств (F, Е), где V— конечное множество элементов, называемых вершинами графа, а Е — конечное множество упорядоченных пар е = (и, v), называемых дугами, где u,v — вершины.
Говорят, что дуга е выходит из вершины и и входит в вершину v. Вершины и и v называют инцидентными дуге е, а дугу е — инцидентной вершинам и и v.
В этом определении множество вершин V соответствует множеству узлов моделируемой сети, а множество дуг — связям между узлами. Определение, данное выше, отражает лишь структуру сети, но не характеристики ее отдельных узлов и связей. Если такие характеристики все же существенны, то рассматривают нагруженные графы, в которых с каждой вершиной или дугой (может быть, и с тем, и с другим) связана величина или несколько величин, называемых нагрузкой на граф. Формально говоря, нагрузку графа определяют функции:
/: V-+W, и g: E-*W2,
где W\ и W2 представляют собой множества значений нагрузки вершин и дуг графа соответственно. Иногда при анализе графа неважно, какая из вершин и и v в дуге е = (и, v) первая, а какая вторая, т. е. пара (w, v) не упорядочена. В этом случае дугу е называют ребром, а весь граф называют неориентированным в отличие от ориентированного графа, задаваемого исходным определением. Разумеется, в этом случае бессмысленно говорить о том, из какой
Способы представления структур данных
45
вершины ребро выходит и в какую вершину входит. Формально говоря, неориентированным графом называют такой граф, у которого наряду с любой дугой е\ = (w, v) имеется и противоположная дуга ег = (v, и). Эта пара дуг и образует ребро е = <и, v> неориентированного графа.
При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор представления графа определяется прежде всего тем, какие алгоритмы обработки графов используются, а также соображениями экономии памяти при обработке очень больших графов или в условиях жестких ограничений на расход памяти.
Говоря о представлении графа, имеют в виду прежде всего вопрос о представлении в памяти его структуры, т. е. считается, что по представлению графа нужно уметь определять, какие вершены с какими другими вершинами в графе связаны. На практике кроме структуры графа нужно каким-то образом представлять и нагрузку на его вершины и дуги. От того, какие элементы графа нагружены и какого типа эта нагрузка, тоже зависит представление графа.
Ниже приводится несколько способов представления графов, причем для каждого способа указано, для каких алгоритмов он подходит, а также дана приблизительная оценка занимаемой памяти. Везде далее считается, что число вершин графа N = card(V) и число дуг (или ребер) графа М = card(E) — величины постоянные. Можно считать, что вершины графа имеют номера от 0 до ЛМ, а каждая дуга характеризуется парой номеров вершин, инцидентных этой дуге.
В листингах будем представлять только структуру графов, причем для каждого способа представления опишем только конструктор соответствующего класса и операции добавления новой дуги и проверки наличия дуги с заданными концами. Для простоты опущены деструкторы графов и некоторые другие, несущественные для данного раздела, подробности. Поскольку большинство операций, представленных ниже в листингах, одинаковы для всех представлений графов, имеет смысл описать абстрактный класс Graph, в котором и определить все эти операции в виде пустых виртуальных функций. Тогда конкретные представления графов будут описаны в виде классов, производных от базового класса Graph.
Первое из описываемых представлений графа основано на следующих соображениях. Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из нее, причем каждая дуга, выходящая из вершины и, идентифицируется своим концом— номером вершины, в которую эта дуга входит. Таким образом, граф представляется массивом, в котором каждому номеру вершины и в диапазоне от 0 до N сопоставлено множество
46
Глава 1
целых чисел — номеров вершин, в которые входят дуги, исходящие из выбранной вершины и. Описанное представление графа будем называть S-графом (от set— множество). Будем считать, что множество целых чисел в диапазоне от 0 до N представлено объектом класса Set из разд. 1.4. Тогда S-граф может быть описан следующим классом (в листинге 1.9 представлено описание абстрактного класса Graph и производного класса SetGraph).
//------------файл graph.h
class Graph {
public:
// Функция addArc позволяет добавить к графу новую дугу,
// ведущую из вершины с номером from в вершину с номером to. virtual void addArc (int from, int to) = 0;
// Функция hasArc проверяет, имеется ли в графе дуга, ведущая //из вершины с номером from в вершину с номером to. virtual bool hasArc(int from, int to) const = 0;
Предыдущая << 1 .. 10 11 12 13 14 15 < 16 > 17 18 19 20 21 22 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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