Анализ ёмкостной сложности

Для определения ёмкостной сложности программы необходимо определить размер динамического списка и матрицы смежности.

Размер динамического списка и матрицы смежности зависит от заданного списка окрестностей, в частности от количества строк и количества чисел в каждой строке.

Каждый узел динамического списка, использующегося в программе, имеет следующую структуру:

struct DirectedGraph {

ArcGraph oneArc;

DirectedGraph *previousArc;

DirectedGraph *nextArc;

};

В состав данной структуры входят: переменная-представитель структурного типа ArcGraph oneArc, два указателя типа int (под данные типа int отводится четыре байта). Так как структура ArgGraph состоит из двух переменных типа int, то переменная oneArc имеет размер 8 байт. И этого следует, что данная структура имеет размер 4+4+8 = 16 байт.

Матрица смежности имеет тип bool, то есть каждый элемент матрицы будет иметь размер 1 байт.

Так же в программе содержатся: указатель на объект класса ostream, занимающий 80 байт, объект класса fstream, занимающий 184 байта, объект класса string, занимающий 32 байта, пять переменных типа short, каждая из которых занимает 2 байта, три переменных типа int, занимающих по 4 байта, переменная типа bool, занимающая 1 байт и семнадцать переменных типа char, занимающих по 1 байту.

Приняв за M количество дуг в графе, за N количество вершин, а так же с учётом памяти, занимаемой всеми переменными, мы получим следующую формулу:

Формула 2

4. Заключение

Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая:

· Вводить список окрестностей ориентированного графа из файла;

· Выводить на экран или в файл список окрестностей и степени исхода всех вершин;

· Находить вершину с наибольшей степенью исхода;

· Удалять вершины, смежные с вершиной, имеющей наибольшую степень исхода;

· Составлять матрицу смежности и выводить её на экран или в файл.

 

5. Список использованной литературы

«C/C++ программирование на языке высокого уровня» Т. А. Павловская.

«Полный справочник по С++, 4-е издание» Герберт Шилдт

«Теория графов» В. В. Белов, У. М. Воробьёв.

 

6. Решение контрольных примеров