Новосибирский Государственный Технический Университет
Контрольная работа.
Коллекция данных – граф.
Выполнил: студент 3 курса
группы ЗФ-322
Белич Владимир
Проверила: Романенко Т. А.
Новосибирск 2016
Цели работы
Спроектировать и реализовать АТД «Ориентированный взвешенный граф».
Задание
Спроектировать, реализовать и протестировать АТД «Ориентированный взвешенный граф» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой. Граф представляет совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).
Интерфейс АТД «Граф» включает операции:
· Конструктор пустого графа для заданных числа вершин, типа, и формы представления
· V() опрос числа вершин в графе,
· E() опрос числа ребер в графе,
· Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,
· Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,
· Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,
· SetEdge(v1,v2, data) задание параметров ребра,
Для визуализации коллекции интерфейс АТД «BST – дерево» включает дополнительную операцию:
· вывод структуры графа на экран,
Реализация АТД «Ориентированный взвешенный граф». Граф представлен в виде списков смежности. Алгоритм определения вершин, удаленных от заданной вершины в пределах заданного по весу расстояния.
Описание АТД «Граф»
Разработанный абстрактный тип данных представляет собой структуру, основанную на списках смежности.Доступ к данным осуществляется по значению индекса вершины
Данные:
Параметры:
size_t_vertexCount – текущее количество вершин в графе
size_t_maxVertexCount–лимит выделенной памяти
Структура данных:
Граф на списках смежностиVertex<Weight, Vert> **vertices
Операции:
Конструктор класса Graph
Вход: нет
Предусловия: нет
Процесс: создание пустого графа
Выход: нет
Постусловия: создан пустой граф
Деструктор класса Graph
Вход: нет
Предусловия: нет
Процесс: удаление коллекции
Выход: нет
Постусловия: коллекция удалена
Вставка ребра в граф
Вход: вершина, из которой исходит ребро from; вершина, в которую входит ребро to; вес ребра weight
Предусловия: вершины существуют; начальная и конечные вершины различаются; между заданными вершинами не существует ребра
Процесс: вставка ребра в граф
Выход: возврат булевского true в случае успешной вставки, false в случае невыполнения предусловия
Постусловия: нет
Вставка вершины в граф
Вход: данные добавляемой вершины Vert
Предусловия: нет
Процесс: вставка вершины в граф
Выход: нет
Постусловия: увеличение счётчика вершин, вершина добавлена в конец списка вершин
Вывод графа на экран
Вход: нет
Предусловия: нет
Процесс: вывод графа на экран
Выход: нет
Постусловия: нет
Возврат значения количества вершин
Вход: нет
Предусловия: нет
Процесс: возврат значения количества вершин
Выход: число вершин
Постусловия: нет
Проверка существования ребра между вершинами
Вход: номеравершин from и to
Предусловия: нет
Процесс: поиск ребра между вершинами
Выход: trueесли ребро существует, falseв противном случае
Постусловия: нет
Изменение веса ребра
Вход: номеравершин from и to; вес ребра weight
Предусловия: существование вершин from и to
Процесс: изменение веса ребра
Выход: возврат булевского true при успешном изменении; false в обратном случае
Постусловия: вес ребра изменён
Удаление ребра из графа
Вход: две вершины from и to;
Предусловия: существование вершин from и to
Процесс: удаление ребра из графа
Выход: возврат булевского true при успешном удалении; false в обратном случае
Постусловия: ребро удалено из графа
Установление новых данных для вершины
Вход: индекс вершины в графе key, новые данные для вершины Vert
Предусловия: существование вершины в графе
Процесс: установление новых данных для вершины
Выход: возврат булевского true при успешном изменении; false в обратном случае
Постусловия: установлены новые данные для вершины
Описание алгоритма определение вершин, удаленных от заданной вершины в пределах заданного по весу расстояния
Алгоритм рекурсивно выводит цепочку из вершин, до которых можно дойти по рёбрам от заданной вершины. На каждом вхождении в рекурсию, передаваемый вес уменьшается на вес пройденной точки.
Общая идея: Общая идея алгоритма состоит в следующем: для выбранной начальной вершины необходимо найти все не пройденные смежные вершины с достигаемым весом рёбер и повторить поиск для них.
Пошаговое представление:
1. Выбираем начальную вершину, обозначим ее как u, и вес пути, обозначим его как w
2. Запускаем процедуру showPath(u, w)
§ Помечаем вершину u как пройденную
§ Для каждой не пройденной смежной с u вершиной (назовем ее v, а вес ребра от uк vназовем weight) запускаем showPath(v, w - weight)
3. Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными либо вес окажется не достижимым.
Время работы: Процедура showPath вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра {e | begin(e) = u}. Всего таких ребер для всех вершин в графе O(E), следовательно, время работы алгоритма оценивается как O(E + V).
4.КлиентскоеописаниеклассаGraph:
Graph() //конструктор
~Graph() //деструктор
bool insertEdge(unsigned int from, unsigned int to, Weight weight) //вставкаребра
voidaddVertex(Vertdata) //добавлениевершины
voidprint() //выводколлекциинаэкран
size_tvertexCount() //возвращение количества вершин
bool hasEdge(unsigned int from, unsigned int to) //проверкасуществованияребра
bool setEdge(unsigned int from, unsigned int to, Weight weight) //изменениевесаребра
bool delEdge(unsigned int from, unsigned int to) //удалениеребра
bool setVertexData(unsigned int key, Vertdata) //изменениеданныхвершины
Клиентское описание класса Task:
Task(); //конструктор
~Task(); //деструктор
voidshowPath(unsignedintfrom, Weightweight); // определение вершин, удаленных от заданной вершины в пределах заданного по весу расстояния
Выводы
В результате проделанной работы был создан абстрактный тип данных — взвешенный ориентированный граф. Работоспособность класса была проверена с помощью созданной программы-меню, дающей доступ ко всем публичным методам созданного класса.
Создан класс задачи, реализующий алгоритм определения вершин, удаленных от заданной вершины в пределах заданного по весу расстояния.
ПриложениеА