Разработка программы формирования матрицы смежности
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ершин;
Находить вершину с наибольшей степенью исхода;
Удалять вершины, смежные с вершиной, имеющей наибольшую степень исхода;
Составлять матрицу смежности и выводить её на экран или в файл.
Список использованной литературы
C/C++ программирование на языке высокого уровня Т. А. Павловская.
Полный справочник по С++, 4-е издание Герберт Шилдт
Теория графов В. В. Белов, У. М. Воробьёв.
Решение контрольных примеров
Пример 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, получим:
проходов по циклам.
Анализ ёмкостной сложности:
В данном примере количество дуг M = 38, количество вершин N = 17. Теперь рассчитаем ёмкостную сложность для данного примера:
байт памяти.
Результаты работы программы:
Пример 2
Исходный граф:
Граф после удаления:
Анализ временной сложности:
Для вычисления количества проходов по циклам воспользуемся формулой 1:
проходов по циклам.
Анализ ёмкостной сложности:
В данном примере количество дуг M = 65, количество вершин N = 31. Исходя из этого, рассчитаем ёмкостную сложность:
байт памяти.
Результаты работы программы:
Пример 3
Исходный граф:
Граф после удаления:
Анализ временной сложности:
Воспользовавшись формулой 1, рассчитаем временную сложность программы для данного примера (количество дуг M = 181, , N = 77):
проход по циклам.
Анализ ёмкостной сложности:
В данном примере количество дуг M = 181, количество вершин N = 77. Исходя из этого, вычислим ёмкостную сложность программы для данного примера по формуле 2:
байт памяти.
Результаты работы программы:
4.Исходный код программы:
#include "stdafx.h"
#include
#include
#include
#include namespace std;ArcGraph {outVertexId;inVertexId;
};DirectedGraph {oneArc;*previousArc;*nextArc;
};_input(int &var) {BAD_STATE = 2;{.clear();.sync();>> var;
} while(cin.rdstate() == BAD_STATE);
}_input(char &output, char mode = b) {char OUTPUT_MODE = o, ASK_MODE = b, MAIN_MODE = m, SOME_ACTIONS_MODE = s;successfulInput;{.sync();>> output;(output == e) exit(0);(mode) {OUTPUT_MODE: successfulInput = (output == f || output == s); break;ASK_MODE: successfulInput = (output == y || output == n); break;MAIN_MODE: successfulInput = (output == p || output == m || output == d || output == r); break;SOME_ACTIONS_MODE: successfulInput = (output == p || output == m || output == s || output == r); break;
}
} while(!successfulInput);
}_input(string &var) {.sync();(cin, var);
}fileExists(string fileName) {(ifstream(fileName) != NULL);
}main() {(LC_ALL, "Russian");("cls");DirectedGraph *firstArc, *sideNode;ostream *out;fstream fileForOutput;string fileForOutputName;short CURRENT_STAGE = 0;int vertexWithMaxLevel, maxLevel, NUM_VERTEX = 0;bool **adjacencyMatrix, fileOutput;char action;static short START_EXECUTION = 0, INPUT_DATA = 1, THE_MAIN_PART = 2, SOME_ACTIONS_PERFORMED = 3;static char ASK_MODE = b, MAIN_MODE = m, SOME_ACTIONS_MODE = s,= y, NO = n,_THE_SCREEN = s, INTO_A_FILE = f,_INPUT = i, FOR_OUTPUT = o, FOR_APPEND = a,_NEIBORHOODS = p, MAKE_ADJACENCY_MATRIX = m, DELETE_VERTEX = d, RESTART_PROGRAM = r, SAVE_NEW_GRAPH = s, EXIT = e;*assembleGraph(int &NUM_VERTEX, ostream *stream);openFile(string fileName, char mode);findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevel, ostream *stream);**completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX);saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX);removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel);removeNode(DirectedGraph *node, DirectedGraph *&firstNode);printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "");printMatrix(bool **matrix, int dimension, ostream *stream, string title = "");clearMatrix(bool **matrix, int dimention);(CURRENT_STAGE) {START_EXECUTION:
cout << "Режим ввода данных (f - в файл, s - на экран, e - выход): ";
_input(action, FOR_OUTPUT);(action) {ON_THE_SCREEN:= &cout;= false;;INTO_A_FILE:
cout << "Имя файла для записи (расширение не требуется): ";
_input(fileForOutputName);(fileExists("output/"+fileForOutputName+".txt"))= openFile("output/"+fileForOutputName+".txt", FOR_APPEND);= openFile("output/"+fileForOutputName+".txt", FOR_OUTPUT);= &fileForOutput;= true;;
}_STAGE = INPUT_DATA;;INPUT_DATA:= assembleGraph(NUM_VERTEX, out);_STAGE = THE_MAIN_PART;;THE_MAIN_PART:
cout << "Список доступных действий:" << endl;<< PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl;<< MAKE_ADJACENCY_MATRIX << " - составить и вывести матрицу смежности" << endl;<< DELETE_VERTEX << " - удалить смежные с вершиной, имеющей наибольшую степень исхода, вершины" << endl;<< RESTART_PROGRAM << " - начать выполнение программы сначала" << endl;
cout << EXIT << " - выход" << endl;
_input(action, MAIN_MODE);(action) {PRINT_NEIBORHOODS:(firstArc, out, NUM_VERTEX, false, "Граф задан следующим списком окрестностей:");
*out << endl << endl;(fileOutput)
cout << "Список окрестностей исходного графа записан в файл." << endl;;MAKE_ADJACENCY_MATRIX:= completeAdjacencyMatrix(firstArc, NUM_VERTEX);(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности исходного графа: ");(adjacencyMatrix, NUM_VERTEX);
*out << endl << endl;
if(fileOutput)<< "Матрица смежности исходного графа записана в файл." << endl;;DELETE_VERTEX:= findVertexAndPrintNewList(firstArc, NUM_VERTEX, maxLevel, out);
*out << endl;_VERTEX -= maxLevel;(firstArc, NUM_VERTEX, vertexWithMaxLevel, maxLevel);
if(fi