Разработка программы формирования матрицы смежности
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Аннотация
В данной пояснительной записке приведено описание программы формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа и работа с этим графом, формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Программа написана на языке C++ в интегрированной среде разработки Microsoft Visual Studio 2005. Так же в данной пояснительной записке представлены результаты работы программы, проведён анализ временной и ёмкостной сложности алгоритма.
Содержание
матрица смежность вершина граф алгоритм
Аннотация
Содержание
.Теоретическая часть
.Программная часть
.Анализ временной и ёмкостной сложности
.Заключение
.Список используемой литературы
.Решение контрольных примеров
.Исходный код программы
1.Теоретическая часть
Графом называется пара (X,U), где X - конечное множество вершин, а U - набор неупорядоченных и упорядоченных пар вершин. Обозначим граф G=(X,U). Неупорядоченная пара вершин называется ребром, упорядоченная - дугой. Граф, содержащий только ребра, называется неориентированным, только дуги - ориентированным, или орграфом.
Если вершины v и u соединены ребром e, то говорят, что они смежны между собой, а ребро e инцидентно каждой из них. Количество ребер графа, инцидентных вершине v называется степенью данной вершины. Для ориентированного графа выделяют входящую степень, равную количеству входящих ребер и исходящую степень, равную количеству исходящих ребер, а степенью вершины в таком случае называют сумму ее входящей и исходящей степени. Вершины, имеющие степень 0, называют изолированными.
Для орграфа на рис.3 входящие степени вершин 1,2,3,4,5 равны соответственно 0,1,1,1,0, исходящие - 2,0,0,1,0. Степени вершин, получаемые сложением входящих и исходящих степеней равны 2,1,1,2,0. Таким образов, вершина 5 - изолированная.
Ребро, соединяющее вершину саму с собой, называется петлей. Если одну пару вершин соединяют два или более ребер, то такие ребра называют кратными. Граф называется простым, если он не содержит ни петель, ни кратных ребер, иначе граф называется мультиграфом. (В некоторых источниках граф с кратными ребрами называют мультиграфом, с петлями - псевдографом). Простой граф, любая пара вершин которого соединена ребром, называется полным.
Граф называется разреженным, если общее количество ребер значительно меньше их возможного количества. Иначе граф называется плотным.
2.Программная часть
Общие сведения
Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа написана на языке программирования C++ в интегрированной среде разработки Microsoft Visual Studio 2005. Программа имеет имя Курсовая работа (программ. 2 семестр).
Программа содержит около 560 строк кода и занимает около 116 КБ на жёстком диске.
Структурная схема
Программа Курсовая работа программ. 2 семестр разбита на функции, что значительно упрощает написание и отладку исходного кода. Структурная схема представлена на рисунке 2.1.
Список функций
Для решения поставленной задачи выполняются следующие функции:
void _input(int &var),_input(char &output, char mode = b),_input(string &var)
Перегруженная функция _input. Служит, чтобы обезопасить программу от ввода неверных данных. В качестве одного из параметров принимает значение типа int, string или char, передаваемое по ссылке.
bool fileExists(string fileName)
Функция проверяет фалй на существование. Функции в качестве аргумента типа string передаётся имя файла. Возвращается true, если файл существует, или false, если файл с указанным именем не найден.
void main()
Точка входа в приложение.
DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream)
Функция, собирающая динамический список по элементам. В качестве параметров принимает переменную типа int, NUM_VERTEX, передаваемую по ссылке, которая впоследствии будет хранить количество вершин заданного графа. Так же указатель *stream на поток вывода данных.
bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout)
Данная функция производит чтение из файла, содержащего список окрестностей вершин, одного значения за один вызов. Принимает параметр graphName типа string, принимающий значение имени файла без расширения, в котором хранится граф, параметр NUM_VERTEX типа int, передающийся по ссылке, ссылку на указатель lastNode типа DirectedGraph, а так же ссылку на поток вывода данных. Функция возвращает значение типа bool, показывающее, прекратился ли ввод информации или нет.
int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevelOfVertex, ostream *stream)
Функция выводит на экран или в файл степени всех вершин, а так же определяет идентификатор вершины, имеющей максимальную степень исхода, и возвращает его. В качестве аргументов принимает указатель на первый элемент динамического списка, количество вершин графа, пустую переменную maxLevelOfVertex, которая принимает значение в теле данной функции, а так же указатель на поток вывода информации.
bool foundInArray(int value, int *arr, int NUM_ITEMS)
Функция принимает в качестве аргументов значение, наличие которого в массиве необходимо определить, указатель на одномерный массив типа int и количество элементов массива. Возвращает истину, если в массиве есть элемент с заданным значением, или ложь, если в массиве такого элемента нет.
fstream openFile(string fileName, char mode)
Функция открывающая файл для заданного режима: I - чтение,