Разработка абстрактного типа данных «Простой граф»

Министерство образования и науки Российской Федерации Новосибирский Государственный Технический Университет Курсовой проект по «Структурам и алгоритмам обработки данных» Группа: АП-318 Студент: Иванчиков И.В. Преподаватель: Романенко Т.А. г. Новосибирск. 2006 г.

Содержание

Задание к курсовому проекту. 3

АТД простой граф. 4

Клиентское описание класса простой граф. 6

АТД класса итератор. 7

Клиентское описание класса итератор. 8

АТД класса DFS. 9

Клиентское описание класса DFS. 9

АТД класса TSORT. 10

Клиентское описание класса TSORT. 10

АТД класса SPT. 11

Клиентское описание класса SPT. 11

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

Описание методики тестирования трудоемкости операций. 13

Задача 1. 13

Задача 2. 15

Задача 3. 16

Описание интерфейса визуализатора. 19

Заключение. 21

Список литературы.. 22

Приложение. 23

Задание к курсовому проекту

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

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

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

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

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

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

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

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

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

Insert(v1,v2)  вставка ребра, соединяющего вершины v1, v2,

Delete (v1,v2)           удаление ребра, соединяющего вершины v1, v2,

Edge(v1,v2)   опрос наличия ребра, соединяющего вершины v1, v2,

SetEdge(v1,v2, data)                        задание параметров ребра,

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

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

Iterator. off( ) опрос окончания просмотра смежных вершин,

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

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

Задача 1

На основе АТД «Простой граф» реализовать интерфейс неориентированного графа для реализации алгоритма, заданного вариантом. Провести эмпирическое исследование времени и вычислительной сложности алгоритма для графов со следующими параметрами:

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

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

8)  определение непересекающихся циклов

Задача 2

На основе АТД «Простой граф» реализовать интерфейс ориентированного графа для реализации алгоритма, заданного вариантом. Провести эмпирическое исследование времени и вычислительной сложности алгоритма для графов со следующими параметрами:

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

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

12)  топологической сортировки ациклического орграфа DAG на основе очереди истоков

Задача 3

На основе АТД «Простой граф» реализовать интерфейс взвешенного графа для реализации алгоритма, заданного вариантом. Провести эмпирическое исследование времени и вычислительной сложности алгоритма для графов со следующими параметрами:

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

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

4)  определение списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины взвешенного орграфа с отрицательной весовой функции на основе алгоритма Беллмана-Форда

АТД простой граф.

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

Данные:

          Параметры:

                        Указатель на класс представления графа, кол-во вершин и ребер хранится в представлениях L-graph (список смежности) и M-graph (матрица смежности).

Операции:

Конструктор:

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

                Предусловия: нет.

Процесс: создание объекта класса представления графа (списки смежности), в соответствии с полученными параметрами.

Постусловия: Способ представления – Списки смежности; E – количество ребер – 0; maxE – максимальное количество рёбер.

Выход: нет.

Деструктор:

                Вход: нет.

                Предусловия: нет

Процесс: удаление объекта класса представления.

Постусловия: нет.

Выход: нет.

Опрос количества вершин в графе:

                Вход: Нет.

                Предусловия: нет.

Процесс: Чтение текущего количества вершин.

Постусловия: нет.

Выход: количество вершин в графе.

Опрос количества рёбер в графе:

                Вход: Нет.

                Предусловия: нет.

Процесс: Чтение текущего количества рёбер.

Постусловия: нет.

Выход: количество рёбер в графе.

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

                Вход: Нет.

                Предусловия: нет.

Процесс: опрос типа графа.

Постусловия: нет.

Выход: true – ориентированный, false - неориентированный.

Опрос способа представления графа: