Создан заказ №4056473
25 мая 2019
Создание графа, используя список смежности, нахождение радиуса при помощи BFS, на основе с++ без STL
Как заказчик описал требования к работе:
Подготовка исходных данных для решения задачи.
Подготовить используя средство отрисовки графов yEd Graph Editor (загрузить можно по ссылке https://www.yworks.com/products/yed/ - лицензия GNU) 3 графа:
Граф 1: 7 вершин и 7-14 дуг (необходимое количество дуг в зависимости от варианта)
Граф 2: 15 верш
ин и 15-20 дуг (необходимое количество дуг в зависимости от варианта)
Граф 3: 20 вершин и 20-40 дуг (необходимое количество дуг в зависимости от варианта)
Необходимо сохранить нарисованные графы в двух форматах:
GraphML — язык описания (иногда упоминается как отдельный формат файлов) графов на основе XML.
Trivial Graph Format («простой формат графов», сокр. TGF) — простой формат файлов, основанный на тексте, для описания графов.
При этом потребуется изобразить неориентированный граф в виде ориентированного графа, но с двунаправленными ребрами, как показано, например, на рисунке ниже.
Для графа 1 необходимо подтвердить полученный результат вручную поэтапно показав, как был получен именно этот результат.
Для графов 2 и 3 нужно привести скриншот работы программы. Необходимо, используя граф 2 и 3, показать наиболее сложные с точки зрения алгоритма случаи работы программы.
Шаг 2. Реализация алгоритма чтения формата хранения графов TGF.
Студенту необходимо реализовать ввод данных графов через файлы в формате TGF.
Ниже приводится содержимое файла в формате TGF для изображенного выше графа:
1 v1
2 v2
3 v3
4 v5
5 v4
6 v6
7 v7
#
1 2 18
2 1 18
2 3 8
3 2 8
3 5 7
5 3 7
5 4 5
4 5 5
4 6 6
6 4 6
1 7 7
7 1 7
7 6 15
6 7 15
1 4 14
4 1 14
Таким образом, необходимо реализовать загрузку данных графа используя формат TGF, для разрабатываемой программы.
Шаг 3. Реализовать необходимый алгоритм в соответствии с заданным вариантом задания (необходимые материалы приведены в разделе необходимые сведения из теории).
Шаг 4. Адаптировать разработанный алгоритм на шаге 3 для заданного в варианте способа представления графа.
Шаг 5. Протестировать разработанное программное обеспечение.
Шаг 6. Оформить отчет по курсовой работе.
Отчет по курсовой работе оформляется в соответствии с требованиями, предъявляемыми к оформлению курсовых работ в вузе (Инструкция по организации и проведению курсового проектирования должен содержать:
Титульный лист (установленная форма Приложение №1 в *).
Наименование и цель работы (берется из рекомендаций по выполнению КР).
Исходные данные варианта задания (изображения).
Алгоритм решения задачи (сведения и .
Листинг программы с исходными и выходными данными (исходный код должен быть приведен в удобном для чтения формате, с необходимыми комментариями).
Анализ результатов (контрольная распечатка — скриншоты и граф 1,2 и 3).
Выводы.
Индикаторные критерии оценки
Оценка «удовлетворительно»
Реализована загрузка данных графа из файла в формате TGF.
Программа запускается и верно выполняет задание согласно варианту
Студент имеет представление о работе программы.
Оценка «хорошо»
Тоже что и на оценку «удовлетворительно» с применением следующих элементов:
Использование динамической памяти (операция new).
Функции добавления или удаления вершин и дуг в графе.
Функция изменения вершин и дуг (веса или направления) в графе.
Умение объяснить принципы работы разработанной программы.
Оценка «отлично»
Тоже что и на оценку «хорошо», дополнительно
Использование классов и объектов для решения поставленной задачи согласно варианту с применением следующих элементов:
Конструкторов и деструкторов.
Друзья классов.
Наследование (простое или множественное).
Перегрузка операций.
Виртуальные функции.
Функция FIRST(v), которая возвращает индекс первой вершины в графе.
Функция NEXT(v, i), которая возвращает индекс вершины, смежной с вершиной v, следующий за индексом i.
Функция VERTEX(v, i), которая возвращает вершину с индексом i из множества вершин, смежных с v.
алгоритм --Определить внешний радиус не взвешенного неориентированного графа методом обхода в ширину. (Внешним радиусом графа будем называть наибольшее среди кратчайших расстояние от центра до какого-либо узла.) Вывести значение, а также соответствующие ему цепи.
способ представления графа -- Список смежности
подробнее
Заказчик
заплатил
заплатил
500 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
28 мая 2019
Заказ завершен, заказчик получил финальный файл с работой
5
Создание графа, используя список смежности, нахождение радиуса при помощи BFS, на основе с++ без STL.docx
2019-05-31 17:05
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Очень отзывчивый автор, способный пояснить любой вопрос. Было безумно приятно работать. Работа была выполнена отлично. Ко всем нюансам относится с пониманием.
Хочешь такую же работу?
300 ₽
