Разработка программы формирования матрицы смежности - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Разработка программы формирования матрицы смежности

Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


В данной пояснительной записке приведено описание программы формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа и работа с этим графом, формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Программа написана на языке C++ в интегрированной среде разработки Microsoft Visual Studio 2005. Так же в данной пояснительной записке представлены результаты работы программы, проведён анализ временной и ёмкостной сложности алгоритма.
матрица смежность вершина граф алгоритм
3. Анализ временной и ёмкостной сложности
Графом называется пара (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 - изолированная.
Ребро, соединяющее вершину саму с собой, называется петлей. Если одну пару вершин соединяют два или более ребер, то такие ребра называют кратными. Граф называется простым, если он не содержит ни петель, ни кратных ребер, иначе граф называется мультиграфом. (В некоторых источниках граф с кратными ребрами называют мультиграфом, с петлями - псевдографом). Простой граф, любая пара вершин которого соединена ребром, называется полным.
Граф называется разреженным, если общее количество ребер значительно меньше их возможного количества. Иначе граф называется плотным.
Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа написана на языке программирования C++ в интегрированной среде разработки Microsoft Visual Studio 2005. Программа имеет имя «Курсовая работа (программ. 2 семестр)».
Программа содержит около 560 строк кода и занимает около 116 КБ на жёстком диске.
Программа «Курсовая работа «программ. 2 семестр» разбита на функции, что значительно упрощает написание и отладку исходного кода. Структурная схема представлена на рисунке 2.1.
Для решения поставленной задачи выполняются следующие функции:
void _input(char &output, char mode = 'b'),
Перегруженная функция _input. Служит, чтобы обезопасить программу от ввода неверных данных. В качестве одного из параметров принимает значение типа int, string или char, передаваемое по ссылке.
Функция проверяет фалй на существование. Функции в качестве аргумента типа string передаётся имя файла. Возвращается true, если файл существует, или false, если файл с указанным именем не найден.
· 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 - чтение, 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. На основе считанных из файла данных строится динамический двунаправленный линейный список, хранящий список дуг ориентированного графа.
· список окрестностей вершин, которым задан данный граф;
· степени исхода всех вершин и идентификатор вершины с максимальной степенью исхода;
· список окрестностей вершин графа после удаления вершин, смежных с вершиной, имеющей наибольшую степень исхода;
· *firstNode - указатель на первый узел динамического списка;
· NUM_VERTEX - количество вершин графа
3. Анализ временной и ёмкостной сложности
Для определения временной сложности программы необходимо рассчитать количество итераций циклов в программе.
Количество итераций циклов зависит от количества дуг в графе, а так же от величины идентификатора вершины с максимальной степенью исхода и степени исхода этой вершины.
Пусть M - количество дуг графа, - количество дуг графа после удаления вершин, смежных с вершиной, имеющей максимальную степень исхода (далее - удаление), N - количество вершин графа, - степень исхода вершины. Тогда количество итераций циклов в программе можно вычислить по следующей формуле:
Для определения ёмкостной сложности программы необходимо определить размер динамического списка и матрицы смежности.
Размер динамического списка и матрицы смежности зависит от заданного списка окрестностей, в частности от количества строк и количества чисел в каждой строке.
Каждый узел динамического списка, использующегося в программе, имеет следующую структуру:
В состав данной структуры входят: переменная-представитель структурного типа 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 количество вершин, а так же с учётом памяти, занимаемой всеми переменными, мы получим следующую формулу
Во время выполнения курсовой работы был разработан алгоритм, решающий поставленную задачу. По составленному алгоритму была написана программа, позволяющая:
· Вводить список окрестностей ориентированного графа из файла;
· Выводить на экран или в файл список окрестностей и степени исхода всех вершин;
· Находить вершину с наибольшей степенью исхода;
· Удалять вершины, смежные с вершиной, имеющей наибольшую степень исхода;
· Составлять матрицу смежности и выводить её на экран или в файл.
«C/C++ программирование на языке высокого уровня» Т. А. Павловская.
«Полный справочник по С++, 4-е издание» Герберт Шилдт
«Теория графов» В. В. Белов, У. М. Воробьёв.
Используя формулу 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, получим:
В данном примере количество дуг M = 38, количество вершин N = 17. Теперь рассчитаем ёмкостную сложность для данного примера:
Для вычисления количества проходов по циклам воспользуемся формулой 1:
В данном примере количество дуг M = 65, количество вершин N = 31. Исходя из этого, рассчитаем ёмкостную сложность:
Воспользовавшись формулой 1, рассчитаем временную сложность программы для данного примера (количество дуг M = 181, , N = 77):
В данном примере количество дуг M = 181, количество вершин N = 77. Исходя из этого, вычислим ёмкостную сложность программы для данного примера по формуле 2:
} while(cin.rdstate() == BAD_STATE);
void _input(char &output, char mode = 'b') {
const char OUTPUT_MODE = 'o', ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's';
case OUTPUT_MODE: successfulInput = (output == 'f' || output == 's'); break;
case ASK_MODE: successfulInput = (output == 'y' || output == 'n'); break;
case MAIN_MODE: successfulInput = (output == 'p' || output == 'm' || output == 'd' || output == 'r'); break;
case SOME_ACTIONS_MODE: successfulInput = (output == 'p' || output == 'm' || output == 's' || output == 'r'); break;
return (ifstream(fileName) != NULL);
static DirectedGraph *firstArc, *sideNode;
static int vertexWithMaxLevel, maxLevel, NUM_VERTEX = 0;
static bool **adjacencyMatrix, fileOutput;
const static short START_EXECUTION = 0, INPUT_DATA = 1, THE_MAIN_PART = 2, SOME_ACTIONS_PERFORMED = 3;
const static char ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's',
ON_THE_SCREEN = 's', INTO_A_FILE = 'f',
FOR_INPUT = 'i', FOR_OUTPUT = 'o', FOR_APPEND = 'a',
PRINT_NEIBORHOODS = 'p', MAKE_ADJACENCY_MATRIX = 'm', DELETE_VERTEX = 'd', RESTART_PROGRAM = 'r', SAVE_NEW_GRAPH = 's', EXIT = 'e';
DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream);
fstream openFile(string fileName, char mode);
int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevel, ostream *stream);
bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX);
bool saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX);
void removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel);
void removeNode(DirectedGraph *node, DirectedGraph *&firstNode);
void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "");
void printMatrix(bool **matrix, int dimension, ostream *stream, string title = "");
void clearMatrix(bool **matrix, int dimention);
cout << "Режим ввода данных (f - в файл, s - на экран, e - выход): ";
cout << "Имя файла для записи (расширение не требуется): ";
if(fileExists("output/"+fileForOutputName+".txt"))
fileForOutput = openFile("output/"+fileForOutputName+".txt", FOR_APPEND);
fileForOutput = openFile("output/"+fileForOutputName+".txt", FOR_OUTPUT);
firstArc = assembleGraph(NUM_VERTEX, out);
cout << "Список доступных действий:" << endl;
cout << PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl;
cout << MAKE_ADJACENCY_MATRIX << " - составить и вывести матрицу смежности" << endl;
cout << DELETE_VERTEX << " - удалить смежные с вершиной, имеющей наибольшую степень исхода, вершины" << endl;
cout << RESTART_PROGRAM << " - начать выполнение программы сначала" << endl;
cout << EXIT << " - выход" << endl;
printNeiborhoodsList(firstArc, out, NUM_VERTEX, false, "Граф задан следующим списком окрестностей:");
cout << "Список окрестностей исходного графа записан в файл." << endl;
adjacencyMatrix = completeAdjacencyMatrix(firstArc, NUM_VERTEX);
printMatrix(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности исходного графа: ");
clearMatrix(adjacencyMatrix, NUM_VERTEX);
cout << "Матрица смежности исходного графа записана в файл." << endl;
vertexWithMaxLevel = findVertexAndPrintNewList(firstArc, NUM_VERTEX, maxLevel, out);
removeAdjacentVertex(firstArc, NUM_VERTEX, vertexWithMaxLevel, maxLevel);
cout << "Вершины, смежные с вершиной, имеющей максимальную степень исхода, удалены," << endl
<< "Степени исхода всех вершин записаны в файл." << endl;
CURRENT_STAGE = SOME_ACTIONS_PERFORMED;
cout << "Запись в файл успешно завершена!" << endl;
cout << "Список доступных действий:" << endl;
cout << PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl;
cout << MAKE_ADJACENCY_MATRIX << " - соствить и вывести матрицу смежности" << endl;
cout << SAVE_NEW_GRAPH << " - сохранить новый граф" << endl;
cout << RESTART_PROGRAM << " - начать выполнение программы сначала" << endl;
cout << EXIT << " - выход" << endl;
printNeiborhoodsList(firstArc, out, NUM_VERTEX, false, "Список окрестностей графа после удаления вершин, смежных с вершиной, имеющей максимальную степень исхода:");
cout << "Список окрестностей нового графа записан в файл." << endl;
adjacencyMatrix = completeAdjacencyMatrix(firstArc, NUM_VERTEX);
printMatrix(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности нового графа: ");
clearMatrix(adjacencyMatrix, NUM_VERTEX);
cout << "Матрица смежности нового графа записана в файл." << endl;
cout << "Введите имя нового графа: ";
if(!saveGraph(fileForOutputName, firstArc, NUM_VERTEX))
cout << "Граф с таким именем " << fileForOutputName << " уже существует!" << endl;
cout << "Сохранение графа произведено успешно." << endl;
cout << "Запись в файл успешно завершена!" << endl;
DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream) {
DirectedGraph *firstNode = NULL, *lastNode = NULL, *currentNode;
bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout);
if(getArcData(graphName, NUM_VERTEX, firstNode, stream)) {
while(getArcData(graphName, NUM_VERTEX, lastNode)) {
lastNode->previousArc = currentNode;
bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout) {
fstream openFile(string fileName, char mode);
if(!fileExists(filePath+graphName+".txt")) {
cout << "Графа с таким именем не существует!" << endl << "Будет загружен стандартный файл . . ." << endl;
fileForReadGraph = openFile(filePath+graphName+".txt", 'i');
*stream << "Граф " << graphName << endl;
lastNode = (DirectedGraph*) new (DirectedGraph);
cout << "Память не выделилась!" << endl << "Выполнение программы завершено . . .";
lastNode->oneArc.inVertexId = inVertexId;
lastNode->oneArc.outVertexId = counter;
int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevelOfVertex, ostream *stream) {
int counter, inVertexCounter, vertexWithMaxLevel = 0;
for(counter = 1; counter <= NUM_VERTEX; counter++) {
while((firstNode != NULL) && (firstNode->oneArc.outVertexId == counter)) {
*stream << "Степень исхода вершины " << counter << ": " << inVertexCounter << endl;
if(inVertexCounter > maxLevelOfVertex) {
maxLevelOfVertex = inVertexCounter;
*stream << "Вершина с максимальной степенью исхода: " << vertexWithMaxLevel << endl;
int foundInArray(int value, int *arr, int rightBound) {
int counter, middle, leftBound = 0;
if((value > arr[rightBound]) || (value < arr[leftBound]))
while((rightBound-leftBound) > 1) {
for(counter = 0; counter <= rightBound; counter++) {
fstream openFile(string fileName, char mode) {
case 'i': filePointer.open(fileName, ios_base::in); break;
case 'o': filePointer.open(fileName, ios_base::out); break;
case 'a': filePointer.open(fileName, ios_base::app); break;
void removeNode(DirectedGraph *node, DirectedGraph *&firstNode) {
if((node->previousArc != NULL) && (node->nextArc != NULL)) {
node->previousArc->nextArc = node->nextArc;
node->nextArc->previousArc = node->previousArc;
} else if((node->previousArc == NULL) && (node->nextArc != NULL)) {
} else if((node->previousArc != NULL) && (node->nextArc == NULL)) {
} else if((node->previousArc == NULL) && (node->nextArc == NULL)) {
bool saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX) {
void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "");
fstream openFile(string fileName, char mode);
if(fileExists("graphs/"+fileName+".txt")) return false;
file = openFile("graphs/"+fileName+".txt", 'o');
printNeiborhoodsList(firstNode, &file, NUM_VERTEX, true);
void removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel) {
DirectedGraph *currentNode, *nodePointer, *sidePointer;
int counter, currentId, *adjacentVertex, *newVertexId, NOT_FOUND = -1;
void removeNode(DirectedGraph *node, DirectedGraph *&firstNode);
int foundInArray(int value, int *arr, int rightBound);
while((currentNode != NULL) && (currentNode->oneArc.outVertexId != vertexId))
currentNode = currentNode->nextArc;
adjacentVertex = new int [vertexLevel];
adjacentVertex[0] = currentNode->oneArc.inVertexId;
currentNode->oneArc.inVertexId = 0;
currentNode = currentNode->nextArc;
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == vertexId)) {
adjacentVertex[counter] = currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
currentId = currentNode->oneArc.outVertexId;
if(foundInArray(currentId, adjacentVertex, vertexLevel-1) != NOT_FOUND) {
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == currentId)) {
currentNode = currentNode->nextArc;
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == currentId))
currentNode = currentNode->nextArc;
newVertexId = new int [NUM_VERTEX];
newVertexId[counter] = currentNode->oneArc.outVertexId;
if(currentNode->oneArc.inVertexId != 0) {
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == newVertexId[counter])) {
currentNode->oneArc.outVertexId = counter+1;
if(foundInArray(currentNode->oneArc.inVertexId, adjacentVertex, vertexLevel-1) != NOT_FOUND) {
currentNode->oneArc.inVertexId = 0;
currentNode = currentNode->nextArc;
currentNode = currentNode->nextArc;
currentNode = currentNode->nextArc;
currentNode->oneArc.outVertexId = counter+1;
currentNode = currentNode->nextArc;
if(currentNode->oneArc.inVertexId == 0) {
currentNode = currentNode->nextArc;
currentId = currentNode->oneArc.outVertexId;
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == currentId)) {
currentNode->oneArc.inVertexId = foundInArray(currentNode->oneArc.inVertexId, newVertexId, NUM_VERTEX-1)+1;
currentNode = currentNode->nextArc;
void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "") {
DirectedGraph *currentNode = firstNode;
currentVertex = currentNode->oneArc.outVertexId;
*stream << endl << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == currentVertex)) {
*stream << ' ' << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
*stream << endl << (currentVertex = currentNode->oneArc.outVertexId) << ": ";
*stream << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
while((currentNode != NULL) && (currentNode->oneArc.outVertexId == currentVertex)) {
*stream << ' ' << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX) {
DirectedGraph *currentNode = firstNode;
int currentId, rowCounter, colCounter;
bool **adjacencyMatrix = new bool* [NUM_VERTEX];
for(rowCounter = 0; rowCounter < NUM_VERTEX; rowCounter++) {
adjacencyMatrix[rowCounter] = new bool [NUM_VERTEX];
for(colCounter = 0; colCounter < NUM_VERTEX; colCounter++)
adjacencyMatrix[rowCounter][colCounter] = false;
if(currentNode->oneArc.inVertexId != 0)
adjacencyMatrix[currentNode->oneArc.outVertexId-1][currentNode->oneArc.inVertexId-1] = true;
currentNode = currentNode->nextArc;
void printMatrix(bool **matrix, int dimension, ostream *stream, string title = "") {
for(rowCounter = 0; rowCounter < dimension; rowCounter++) {
*stream << endl << ' ' << matrix[rowCounter][0];
for(colCounter = 1; colCounter < dimension; colCounter++) {
*stream << ' ' << matrix[rowCounter][colCounter];
void clearMatrix(bool **matrix, int dimention) {
for(int counter = 0; counter < dimention; counter++)
Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа. курсовая работа [145,5 K], добавлен 27.01.2013
Вершина в заданном графе с различным количеством вершин. Результаты обработки графа программой MyProject.exe. Сопряжение модулей программы. Модуль вывода матрицы смежности. Тесты черного ящика. Комбинаторное покрытие условий тестами черного ящика. курсовая работа [44,8 K], добавлен 13.10.2012
Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы. курсовая работа [525,6 K], добавлен 14.07.2012
Пример матрицы смежности для соответствующей сети. Функция распределения степеней узлов. Вариант матрицы смежности для взвешенной сети. Распределение степеней для случайных графов. Требования к интерфейсу. Алгоритм модели Баррат-Бартелэмью-Веспиньяни. контрольная работа [1,4 M], добавлен 13.06.2012
История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7. контрольная работа [646,9 K], добавлен 19.01.2016
Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией. курсовая работа [334,1 K], добавлен 20.01.2013
Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов. курсовая работа [1,1 M], добавлен 26.06.2012
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Разработка программы формирования матрицы смежности курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение: Евгений Онегин - Энциклопедия русской жизни
Реферат: Создание эффективных правовых инструментов надлежащей охраны фонограмм и музыкальных произведений
Как Оформлять Эссе В Тетради
Реферат: Battle Royal Symbolism Essay Research Paper In
Кухни Курсовой
Особенности познания социальной реальности. Эволюция представлений об обществе в истории философской мысли
История Развития Стереометрии Реферат
Реферат по теме Политическое лидерство и политические лидеры
Пример Тезисов К Дипломной Работе
Реферат по теме Документ як засіб комунікації
18 Век Реферат
Экономия воды
Зачем Человеку Космос Сочинение
Курсовая Работа На Тему Анализ Маркетинговой Деятельности
Реферат по теме Мнение авторитетных людей по поводу затопления станции 'Мир'
Доклад: Мягко стелешь - красиво ступаешь
Сочинение Про Устное Народное Творчество
Реферат: Конфигурирование интерфейсов Ethernet на маршрутизаторе
Реферат по теме Мировоззренческие и социально-этические проблемы генетики человека
Дипломная работа по теме Эволюция exercice классического танца
Контроль и ревизия на предприятии - Бухгалтерский учет и аудит контрольная работа
Местное самоуправление. История и структура власти в г. Ростове-на-Дону - Государство и право реферат
Организация учета поступления основных средств - Бухгалтерский учет и аудит курсовая работа