Шифр 04. Спроектировать и реализовать универсальную программную коллекцию для АТД (абстрактный тип данных) «Простой граф» и использовать коллекцию для решения задач

  • ID: 34467 
  • 70 страниц

Фрагмент работы:

КУРСОВОЙ ПРОЕКТ

«Структуры и алгоритмы обработки данных»

Задание

Спроектировать и реализовать универсальную программную коллекцию для АТД

(абстрактный тип данных) «Простой граф» и использовать коллекцию для решения

задач для неориентированных, ориентированных и взвешенных графов.

Разработать АТД «Вершина графа».

Интерфейс АТД «Ребро графа» включает операции:

Конструктор с параметрами: имя вершины, данные, связанные с вершиной,

GetName( ) опрос имени вершины,

GetData( ) опрос данных, связанных с вершиной,

SetName(name) задание имени вершины,

SetData(data) задание данных, связанных с вершиной,

Разработать АТД «Ребро графа».

Интерфейс АТД «Ребро графа» включает операции:

Конструктор с параметрами: имя вершины, из которой исходит ребро, имя вершины,

в которую входит ребро, данные ребра,

v1( ) опрос имени вершины, из которой исходит ребро,

v2( ) опрос имени вершины, в которую входит ребро,

from (v) опрос признака исхода ребра из вершины v,

other(v) опрос имени вершины, связанной с вершиной v данным ребром,

GetW ( ) опрос веса ребра,

GetData( ) опрос данных, связанных с ребром,

SetW (w) задание веса ребра,

SetData(data) задание данных, связанных с ребром.

Разработать АТД «Простой граф».

Интерфейс АТД «Простой граф» включает операции:

Конструктор пустого графа для заданных числа вершин, типа (ориентированный /

неориентированный), и формы представления(ориентированный / неориентированный)

V( ) - опрос числа вершин в графе,

E( ) - опрос числа ребер в графе,

Directed( ) опрос типа графа (ориентированный / неориентированный)

Dense( ) опрос формы представления графа (L- граф / M- граф),

K( ) опрос коэффициента насыщенности графа,

ToListGraph() преобразование графа к L- графу,

ToMatrixGraph() преобразование графа к M- графу,

Vertex(v) опрос наличия вершины,

Insert(v) вставка вершины,

Delete (v) удаление вершины v,

Edge(e) опрос наличия ребра e,

Insert(e) вставка ребра e,

Delete (e) удаление ребра e,

Iterator(v) создание итератора смежных вершин для вершины v,

Iterator. off( ) опрос состояния итератора,

Iterator.beg( ) установка итератора на первую смежную вершину,

Iterator.next( ) переход к следующей смежной вершине,

operator * доступ к данным текущего ребра.

Задача 1

На основе АТД «Простой граф» реализовать интерфейс неориентированного графа для

реализации алгоритма, заданного вариантом. Провести эмпирическое исследование

времени и вычислительной сложности алгоритма для графов со следующими

параметрами:

V = 100; E = 50, 100, 1000, 4950.

V = 1000; E = 100, 1000, 10000, 100000.

Определение вершин отделимости в графе.

Задача 2

На основе АТД «Простой граф» реализовать интерфейс ориентированного графа для

реализации алгоритма, заданного вариантом. Провести эмпирическое исследование

времени и вычислительной сложности алгоритма для графов со следующими

параметрами:

V = 100; E = 50, 100, 1000, 9000,

V = 1000; E = 1000, 10000, 500000.

Вычисление транзитивного замыкания орграфа методом Уоршолла.

Задача 3

На основе АТД «Простой граф» реализовать интерфейс взвешенного графа для

реализации алгоритма, заданного вариантом. Провести эмпирическое исследование

времени и вычислительной сложности алгоритма для графов со следующими

параметрами:

V = 100; E = 50, 100, 1000, 4950,

V = 1000; E = 100, 1000, 10000, 200000.

Определение входящих в заданную вершину кратчайших путей на основе алгоритма

Дейкстры.

Форматы АТД

Формат АТД «Граф»

АТД «ГРАФ»

Общая характеристика:

Граф представляет собой объект, состоящий из заданного числа вершин, связанных

некоторым количеством ребер. С ребрами связаны данные - вес ребра указанного

типа Т, с вершинами - данные указанного типа T1. При создании графу задается

количество вершин, которое не может изменяться в процессе работы.

ДАННЫЕ:

ОПЕРАЦИИ:

КОНЕЦ АТД

АТД «ИТЕРАТОР»

КОНЕЦ АТД

Определение шаблонного класса «Граф», предназначенное для клиентской программы

template

template

class CGraph : public CGenericGraph

{

protected:

class CListGraph : public CGenericGraph

{

protected:

struct CNodeData

{

UINT m_nVertex;

TEdge m_EdgeData;

bool operator==(CNodeData data){ }

};

struct CVertexData{};

CVertexData *m_VertexArray;

public:

CListGraph(UINT nVertexes = 0, bool bDirected = false)

: CGenericGraph(nVertexes, bDirected){}

~CListGraph(){}

bool Insert(UINT vertex1, UINT vertex2) {}

bool Delete(UINT vertex1, UINT vertex2) {}

bool Edge(UINT vertex1, UINT vertex2) {}

bool SetEdge(UINT vertex1, UINT vertex2, TEdge EdgeData) {}

TVertex& VertexData(UINT nVertex) {}

АТД вспомогательных объектов для решения задач

Базовый класс для всех интерфейсов заданий.

ДАННЫЕ:

Параметры:

Указатель на объект класса CGraph – m_ptrGraph

ОПЕРАЦИИ:

Операции интерфейса для первого задания

Общая характеристика:

Клиентский класс, обрабатывающий объект графа. Класс последовательно

просматривает вершины графа, заполняя массив, хранящий количество исходящих

ребер; определяет, на основании данных содержащихся в вышеуказанном массиве,

присутствуют ли в данном графе вершины отделимости. Данные результатов

заносятся в массив, хранящий значение вершин отделимости

ДАННЫЕ:

ОПЕРАЦИИ:

Операции интерфейса для второго задания

Операции интерфейса для третьего задания

Общая характеристика:

Клиентский класс, выполняющий в графе вычисление кратчайших путей из заданной

вершины и выбирающий максимальный из них - эксцентриситет. Вычисление путей

базируется на сумме весов ребер.

ДАННЫЕ:

ОПЕРАЦИИ:

КОНЕЦ АТД

Определение шаблонного класса «Задача 1» , предназначенное для клиентской

программы

class CInterfaceTaskOne : public CBaseInterface

{

protected:

int m_Cnt;

int *m_Spt; //массив, хранящий количество исходящих ребер

int *m_VertexOtd; // массив вершин моста

int m_Count;

int m_Ok; //признак успешности выполнения

int countVertex; // подсчет числа пройденных вершин

int countEdges; // подсчет числа пройденных ребер

CVertexQueue *m_ptrQueue;

CEdgeList *m_ptrListsArray;

int *m_ptrDistArray;

int m_nCurrentComponent;

int m_nAlgorythmType;

int m_nCurrentVertex;

int m_nCurrentAdjVertex;

Определение шаблонного класса «Задача 2», предназначенное для клиентской

программы

class CInterfaceTaskTwo : public CBaseInterface

{

protected:

int **m_MatrixTZG;

CEdgeList m_VertexList;

int m_Time;

int m_nCurrentVertex;

// Алгоритм Уоршолла

bool Uorsholl();

// Функция генерации случайного ребра

void RandomEdge(CVertexPair &Edge);

Определение шаблонного класса «Задача 3», предназначенное для клиентской

программы

class CInterfaceTaskThree : public CBaseInterface

{

protected:

//

// Класс CInterfaceTaskThree::CEdgeData. Создан для заданий.

struct CEdgeData

{

bool m_bEdge; // Признак наличия ребра

GEdgeTask3 m_EdgeWeight; // Вес ребра

short m_Predecessor;

// Конструктор с параметрами класса CInterfaceTaskThree::CEdgeWeight

CEdgeData(bool bEdge = false, GEdgeTask3 EdgeWeight = 0)

: m_bEdge(bEdge), m_EdgeWeight(EdgeWeight), m_Predecessor(0)

// Перегруженный оператор сложения

bool operator >(CEdgeData &data);

Диаграмма взаимосвязи объектов, реализующих АТД «Граф», АТД задач

Класс Абстрактный граф является потомком абстрактного класса Граф и является

реализацией АТД «Простой граф». В свою очередь, класс L-граф также является

потомком абстрактного класса Граф, и представляет собой реализацию

представления графа списком.

Рисунок 2.1 - Диаграмма взаимосвязи объектов

Тестирование задач

Краткое описание алгоритма, теоретическая оценка трудоемкости задачи 1

Для решения задачи был использован алгоритм поиска в глубину. Для каждой

вершины строится дерево DFS. Затем мы проверяем, имеет ли корень дерева DFS

более одного потомка, если да, то эта вершина является вершиной отделимости.

Поиск в графе требует время, пропорциональное для представления графа в виде

списков смежных вершин.

Таблицы и графики с результатами тестирования трудоемкости алгоритма задачи 1

Проведем эмпирическое исследование времени и вычислительной сложности алгоритма

для графа со следующими параметрами:

V = 100; E = 50, 100, 1000, 4950.

V = 1000; E = 100, 1000, 10000, 100000.

Результаты тестирования:

Таблица 3.1 - Тестирование трудоемкости алгоритма задачи 1

Рисунок 3.1 - График результатов тестирования задачи 1 при V=100.

Рисунок 3.2 - График результатов тестирования задачи 1 при V=10000.

Сравнительный анализ теоретической и экспериментальных оценок трудоемкости

алгоритма задачи 1

Как видно из графика для разреженных графов значения трудоемкости, полученные

экспериментальным путем, меньше значения теоретической трудоемкости. Это

объясняется тем, что при построении дерева DFS не все вершины будут включены в

это дерево, а, следовательно, и обработаны. С увеличением коэффициента

насыщенности значения трудоемкости, полученные экспериментальным путем,

приближаются к теоретическим.

Таблицы и графики с результатами тестирования трудоемкости алгоритма задачи 2

Проведем эмпирическое исследование времени и вычислительной сложности алгоритма

для графа со следующими параметрами:

V = 100; E = 50, 100, 1000, 9000,

V = 1000; E = 1000, 10000, 500000.

Результаты тестирования:

Таблица 3.2 - Тестирование трудоемкости алгоритма задачи 2

Рисунок 3.3 - График результатов тестирования задачи 2 при V=100

Рисунок 3.4 - График результатов тестирования задачи 2 при V=1000

Сравнительный анализ теоретической и экспериментальных оценок трудоемкости

алгоритма задачи 2

Как видно из графика значения трудоемкости, полученные экспериментальным путем,

совпадают с значениями теоретической трудоемкости.

3.13. Краткое описание алгоритма, теоретическая оценка трудоемкости задачи 3

3.14. Описание методики тестирования трудоемкости алгоритма задачи 3

3.15. Таблицы и графики с результатами тестирования

трудоемкости алгоритма задачи 3

Проведем эмпирическое исследование времени и вычислительной сложности алгоритма

для графа со следующими параметрами:

V = 500; E = 50, 100, 1000, 5000, 10000,

V = 10000; E = 50, 100, 1000, 5000, 10000.

Результаты тестирования:

Таблица 3. - Тестирование трудоемкости алгоритма задачи 3

Рисунок 3.5 - График результатов тестирования задачи 3 при V=100

Рисунок 3.6 - График результатов тестирования задачи 3 при V=1000

3.16. Сравнительный анализ теоретической и экспериментальных оценок

трудоемкости алгоритма задачи 3

Описание графического интерфейса демонстрационной программы для графа и задач

Выполнение данной работы проводилось в среде Microsoft Visual Studio 6.0.

Заключение

В ходе выполнения данной работы были освоены технологии разработки комплексного

программного обеспечения для решения задач в различных прикладных областях. А

именно была спроектирована и реализована универсальная программная коллекция

для АТД «Простой граф», коллекция была использована для решения задач для

неориентированных, ориентированных и взвешенных графов. Были изучены и

реализованы алгоритмы обработки графа.

В процессе тестирования данных задач были выявлены недостатки, а также была

установлена продолжительность тестирования, зависящая от размера графа

(количества вершин и ребер), Результаты значений экспериментального

тестирования совпали с ожидаемыми..

Список использованной литературы

Роберт Сэджвик. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах

- М: DiaSoft, 2002 г. – 496 с.

Романенко Т.А. Теоретический курс по дисциплине «Структуры и алгоритмы

обработки данных».

Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный

подход и реализация на С++. – СПб.: БХВ-Петербург, 2004 г. – 464 с

Приложения