Методом обхода в ширину вычислить цикломатическую сложность графа (Курсовая, C++)

Работа с уникальностью не менее 50%. Успешно защищена в 2019 году.

Методом обхода в ширину вычислить цикломатическую сложность графа .

Цель данной курсовой работы – проанализировать алгоритм и разработать программу вычисления цикломатической сложности графа, заданного матрицей инцидентности, методом обхода в ширину. Для достижения поставленной цели необходимо решить следующие задачи:

• рассмотреть понятие графа, изучить способы его задания;

• изучить понятия цикломатического числа и сложности графа;

• разработать алгоритм вычисления цикломатической сложности графа методом обхода в ширину;

• проанализировать результаты работы программы.

При выполнении работы была использована современная учебная литература, статьи из журналов по математике, информационным технологиям и программированию, а также информационные и аналитические материалы сети Интернет.

В архиве курсовая работа и исходные коды приложения.

1. Теоретическая часть 4

1.1. Понятие графа и способы его задания 4

1.2. Метод обхода графа в ширину и его особенности 6

1.3. Компоненты связности и цикломатическое число графа 8

2. Практическая часть 12

2.1. Описание алгоритма 12

2.2. Описание основных элементов программы 13

2.3. Блок-схема алгоритма 13

2.4. Результат работы программы 14

Заключение 17

Список использованных источников 18

Приложения 20

Приложение А. Исходный код программы 20

1. Ахо Альфред В. Структуры данных и алгоритмы : учеб. пособие / Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. – М.: Издательский дом «Вильямс», 2000. – 384 с.

2. Бабушкина И.А., Окулов С.М. Практикум по объектно-ориентированному программированию. - М.: БИНОМ, 2009. - 391 с.

3. Горитов А. Н. Структуры и алгоритмы обработки данных в ЭВМ : методические указания по выполнению лабораторных работ студентов всех форм обучения для направления подготовки: 230100.62 – «Информатика и вычислительная техника» / А. Н. Горитов. – Томск: ТУСУР, 2011. – 15 с.

4. Горитов А. Н. Структуры и алгоритмы обработки данных в ЭВМ: учеб. пособие / А.Н. Горитов. – Томск: Томский межвузовский центр дистанционного образования, 2000 – 122 с.

5. Дорогов, В.Г. Основы программирования на языке С: Учебное пособие / В.Г. Дорогов, Е.Г. Дорогова; Под общ. ред. проф. Л.Г. Гагарина. - М.: ИД Форум, НИЦ Инфра-М, 2013. - 224 c.

6. Керниган Брайан У. Язык программирования С : пер. с англ. / Брайан У. Керниган, Денис М. Ритчи. – 2-е изд. – М. : Издательский дом «Вильямс», 2009. – 304 с.

7. Красиков И.А. Структуры и алгоритмы обработки данных в ЭВМ: учебное пособие / И.А. Красиков. – Томск : ФДО, ТУСУР, 2016. – 252 с.

8. Подбельский В.В. Программирование на языке Си: учеб. пособие / В. В. Подбельский, С.С. Фомин. – 2-е изд., доп. – М. : Финансы и статистика, 2004. – 600 с.

9. Поляков В.И., Скорубский В.И. Основы теории алгоритмов. – СПб: СПб НИУ ИТМО, 2012. - 51 с.

10. Окулов С.М. Программирование в алгоритмах / С. М. Окулов. - М.: БИНОМ. Лаборатория знаний, 2002. - 341 с.

11. Серкова, Е.Г. Основы алгоритмизации и программирования: практикум / Е.Г. Серкова. - РнД: Феникс, 2019. - 189 c.

12. Черпаков И.В. Основы программирования: учебник и практикум для прикладного бакалавриата / И.В. Черпаков. - М.: Издательство Юрайт, 2017. - 219 с.

13. Дискретная математика: алгоритмы // Сайт кафедры компьютерных технологий факультета информационных технологий и программирования Санкт-Петербургского государственного университета информационных технологий, механики и оптики [Электронный ресурс]. – Режим доступа: http://rain.ifmo.ru/cat/view.php/theory/graph-spanningtrees/mst-2005 (дата обращения - 25.03.2019).

14. Лекция 29: Динамические структуры данных // Структуры и алгоритмы компьютерной обработки данных // Сайт НОУ «ИНТУИТ» [Электронный ресурс]. – Режим доступа: http://www.intuit.ru/studies/courses/648/504/lecture/11455?page=1 (дата обращения: 26.08.2019).

15. Лекция 45: Алгоритмы на графах. Алгоритмы обхода графа // Структуры и алгоритмы компьютерной обработки данных // Сайт НОУ «ИНТУИТ» [Электронный ресурс]. – Режим доступа: http://www.intuit.ru/studies/courses/648/504/lecture/11474 (дата обращения: 27.08.2019).

16. Массивы в C++ / «M a Ge» [Электронный ресурс]. – Режим доступа: http://itandlife.ru/programming/cpp/massivy-v-c/ (дата обращения - 25.08.2019).Введение 3