Разработка программы формирования матрицы смежности
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
o - запись, a - дозапись. В качестве аргументов передаются имя файла и режим. Возвращает объект класса fstream.
void removeNode(DirectedGraph *node, DirectedGraph *&firstNode)
Данная функция удаляет из динамического списка переданный ей в качестве первого аргумента элемент. Так же передаётся ссылка на указатель на первый элемент динамического списка.
void removeAdjacentVertex(DirectedGraph *&firstArc, int vertexId, int vertexLevel)
Функция удаляет из графа вершины, смежные с заданной (идентификатор заданной вершины передаётся в параметра vertexId). Первый аргумент функции - указатель на первый элемент динамического списка, третий параметр - степень исхода передаваемой вершины.
void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, string title = "")
Функция выводит список окрестностей вершин графа на экран или в файл. Первый параметр - первый элемент динамического списка, второй параметр - указатель на поток вывода, третий параметр - указатель на поток вывода, четвёртый параметр - количество вершин в графе, пятый параметр - заголовок перед выводом на экран или в файл.
bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX)
Функция создаёт и заполняет матрицу смежности для заданного ориентированного графа. В качестве параметров передаются первый элемент динамического списка и количество вершин в графе. Возвращается указатель на двумерный динамический массив.
void printMatrix(bool **matrix, int dimension, ostream *stream, string title = "")
функция, выводящая матрицу на экран или в файл. В качестве аргументов передаются матрица, размерность матрицы указатель на выходной поток и заголовок, соответственно.
void clearMatrix(bool **matrix, int dimention)
функция очищает память, отведённую под матрицу matrix с размерностью dimention.
int getKeyByValue(int value, int *arr, int numItems)
Функция определяет и возвращает номер ключа массива, соответствующий значению value. В качестве параметров принимает значение для поиска, одномерный массив и его размерность.
Входные и выходные данные
Программа получает данные из файла, в котором хранится список окрестностей вершин ориентированного графа. Структура файла должна быть следующей: номер строки означает номер (идентификатор) вершины графа, в каждой строке через пробел записаны идентификаторы вершин, в которые входят дуги, исходящие из текущей вершины. Если вершина не имеет исходящих дуг, то в строке, соответствующей данной вершине стоит 0. На основе считанных из файла данных строится динамический двунаправленный линейный список, хранящий список дуг ориентированного графа.
На выходе выводятся:
имя графа;
список окрестностей вершин, которым задан данный граф;
степени исхода всех вершин и идентификатор вершины с максимальной степенью исхода;
список окрестностей вершин графа после удаления вершин, смежных с вершиной, имеющей наибольшую степень исхода;
матрица смежности нового графа.
Алгоритм одной из функций
Функция completeAjacencyMatrix.
Параметры, принимаемые функцией:
*firstNode - указатель на первый узел динамического списка;
NUM_VERTEX - количество вершин графа
.Анализ временной и ёмкостной сложности
Анализ временной сложности
Для определения временной сложности программы необходимо рассчитать количество итераций циклов в программе.
Количество итераций циклов зависит от количества дуг в графе, а так же от величины идентификатора вершины с максимальной степенью исхода и степени исхода этой вершины.
Пусть M - количество дуг графа, - количество дуг графа после удаления вершин, смежных с вершиной, имеющей максимальную степень исхода (далее - удаление), N - количество вершин графа, - степень исхода вершины. Тогда количество итераций циклов в программе можно вычислить по следующей формуле:
Формула 1
Анализ ёмкостной сложности
Для определения ёмкостной сложности программы необходимо определить размер динамического списка и матрицы смежности.
Размер динамического списка и матрицы смежности зависит от заданного списка окрестностей, в частности от количества строк и количества чисел в каждой строке.
Каждый узел динамического списка, использующегося в программе, имеет следующую структуру:
struct DirectedGraph {oneArc;*previousArc; *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 количество вершин, а так же с учётом памяти, занимаемой всеми переменными, мы получим следующую формулу
Заключение
Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая:
Вводить список окрестностей ориентированного графа из файла;
Выводить на экран или в файл список окрестностей и степени исхода всех ?/p>