Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.
Аннотация к работе
Графом называется пара (X,U), где X - конечное множество вершин, а U - набор неупорядоченных и упорядоченных пар вершин. Неупорядоченная пара вершин называется ребром, упорядоченная - дугой. Граф, содержащий только ребра, называется неориентированным, только дуги - ориентированным, или орграфом. Если вершины v и u соединены ребром e, то говорят, что они смежны между собой, а ребро e инцидентно каждой из них. Количество ребер графа, инцидентных вершине v называется степенью данной вершины.Для решения поставленной задачи выполняются следующие функции: · void _input(int &var), void _input(char &output, char mode = "b"), void _input(string &var) В качестве одного из параметров принимает значение типа int, string или char, передаваемое по ссылке. Данная функция производит чтение из файла, содержащего список окрестностей вершин, одного значения за один вызов. Принимает параметр GRAPHNAME типа string, принимающий значение имени файла без расширения, в котором хранится граф, параметр NUM_VERTEX типа int, передающийся по ссылке, ссылку на указатель LASTNODE типа DIRECTEDGRAPH, а так же ссылку на поток вывода данных. В качестве аргументов принимает указатель на первый элемент динамического списка, количество вершин графа, пустую переменную MAXLEVELOFVERTEX, которая принимает значение в теле данной функции, а так же указатель на поток вывода информации.Для определения временной сложности программы необходимо рассчитать количество итераций циклов в программе. Количество итераций циклов зависит от количества дуг в графе, а так же от величины идентификатора вершины с максимальной степенью исхода и степени исхода этой вершины. Пусть M - количество дуг графа, - количество дуг графа после удаления вершин, смежных с вершиной, имеющей максимальную степень исхода (далее - удаление), N - количество вершин графа, - степень исхода вершины. Тогда количество итераций циклов в программе можно вычислить по следующей формуле: Формула 1 Так же в программе содержатся: указатель на объект класса ostream, занимающий 80 байт, объект класса fstream, занимающий 184 байта, объект класса string, занимающий 32 байта, пять переменных типа short, каждая из которых занимает 2 байта, три переменных типа int, занимающих по 4 байта, переменная типа bool, занимающая 1 байт и семнадцать переменных типа char, занимающих по 1 байту.Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая: · Вводить список окрестностей ориентированного графа из файла;Анализ временной сложности: Используя формулу 1, а так же с учетом того, что M = 38, 16, N = 17, степень исхода вершины 1: 3, степень исхода вершины 2: 2, степень исхода вершины 3: 4, степень исхода вершины 4: 1, степень исхода вершины 5: 2, степень исхода вершины 6: 2, степень исхода вершины 7: 2, степень исхода вершины 8: 1, степень исхода вершины 9: 2, степень исхода вершины 10: 6, степень исхода вершины 11: 3, степень исхода вершины 12: 2, степень исхода вершины 13: 1, степень исхода вершины 14: 1, степень исхода вершины 15: 1, степень исхода вершины 16: 1, степень исхода вершины 17: 4, получим: 626 проходов по циклам.
План
Содержание матрица смежность вершина граф алгоритм
Аннотация
Содержание
1. Теоретическая часть
2. Программная часть
3. Анализ временной и емкостной сложности
4. Заключение
5. Список используемой литературы
6. Решение контрольных примеров
7. Исходный код программы
1.
Вывод
Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая: · Вводить список окрестностей ориентированного графа из файла;
· Выводить на экран или в файл список окрестностей и степени исхода всех вершин;
· Находить вершину с наибольшей степенью исхода;
· Удалять вершины, смежные с вершиной, имеющей наибольшую степень исхода;
· Составлять матрицу смежности и выводить ее на экран или в файл.
Список литературы
«C/C программирование на языке высокого уровня» Т. А. Павловская.
«Полный справочник по С , 4-е издание» Герберт Шилдт