Сиаод

  • 16 янв. 2013 г.
  • 7094 Слова
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ























Расчётно-графическая работа
По дисциплине структуры и алгоритмы обработки данных
«Коллекция данных – граф»














Факультет: АВТФ
Группа: АВТ-918
Студент: Кукарин В.
Преподаватель: Романенко Т.А.












Новосибирск 2012
Оглавление

Оглавление 2Общее задание 3
Диаграмма взаимосвязи объектов 3
Формат АТД «Простой граф» 3
Клиентское определение класса «Простой граф» 4
Формат АТД «Итератор вершин» 7
Клиентское определение класса «Итератор вершин» 7
Формат АТД «Итератор рёбер графа» 8
Клиентское определение класса «Итератор рёбер графа» 8
Формат АТД «Итератор исходящих рёбер вершины» 9
Клиентское определение класса «Итератор исходящих рёбервершины» 9
Формат АТД «Итератор входящих рёбер вершины» 10
Клиентское определение класса «Итератор входящих рёбер вершины» 10
Формат АТД «Задача 1» 11
Клиентское определение класса «Задача 1» 11
Формат АТД «Задача 2» 12
Клиентское определение класса «Задача 2» 12
Описание классов (Прототипы шаблонных классов) 14
Задача определения гамильтонова цикла 16
Задача поиска кратчайших путей изодной вершины 16
Заключение 17
Список использованных источников 18
Приложение A. Листинг программы 19
Приложение В. Скриншоты работы программы 37




Общее задание

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

Диаграмма взаимосвязиобъектов































Рисунок 1. Диаграмма взаимосвязи объектов, реализующих АТД «Простой граф»


Формат АТД «Простой граф»


АТД «Простой граф» представляет собой ассоциативную связную структуру элементов. В графе переменное число вершин, каждая из которых имеет уникальный номер. Граф может быть ориентированным или неориентированным. Вершиныориентированного графа могут быть соединены между собой дугами, каждая из которых характеризуется весом и сопряжёнными с ней данными. Вершины ориентированного графа соединены рёбрами, также содержащими поля «вес» и «данные». Предполагается, что наличие ребра означает симметричное отношение между вершинами, наличие дуги – несимметричное (между вершинами не может быть встречной дуги). Между двумяузлами может быть не более 1 дуги/ребра. Невозможно наличие в графе дуги/ребра, инцидентного только одной вершине (петли).
С точки зрения пользователя граф – множество с определённым на нём двухместным отношением; множество вершин и множество рёбер, соединяющих отдельные пары вершин.


Клиентское определение класса «Простой граф»


Параметры: bool IsDirected – тип графа (ориентированный/нет).Структура данных: В зависимости от того, объект какого производного класса сконструирован, граф представлен в виде списков смежности для каждой из вершин (L-граф), либо матрицы смежности (М-граф).

Операции

Конструктор
Вход: Булевский признак ориентированности; без входных параметров по умолчанию создастся неориентированный граф.
Предусловия: Нет.
Процесс: Создание графа без вершин и рёбер.Выход: Нет.
Постусловия: Создан новый граф без элементов.

Конструктор копирования
Вход: Ссылка на объект графа.
Предусловия: Нет.
Процесс: Создание графа – копии входного.
Выход: Нет.
Постусловия: Граф, все его узлы созданы.

Конструктор
Вход: Начальное число элементов и булевский признак ориентированности.
Предусловия: Нет.
Процесс: Создание графа без рёбер с заданным числом вершин.Выход: Нет.
Постусловия: Создан новый граф, вершины которого пронумерованы по порядку целыми числами от нуля.

Конструктор
Вход: Начальное число элементов, начальное число дуг/рёбер и булевский признак ориентированности.
Предусловия: Число рёбер (дуг) не должно превышать максимально возможное количество, способное поместиться в неорграф (орграф).
Процесс: Создание графа...
tracking img