Транзитивным графом называется такой граф, в котором из существования дуг (xi, xj) и (xj, xk) следует существование дуги (xi,xk). Транзитивным замыканием графа G называется граф G’=(V, E∪E’), где E’ — минимальное множество дуг , которое следует добавить к графу G, чтобы он стал транзитивным.
Сегодня мы рассмотрим реализацию алгоритмы транзитивного замыкания графа. Существует несколько способов произвести расчёт: обычный (сложность N^4) и улучшенный (сложность N^3)
Исходный файл: input_graph.txt
|
1 2 3 4 |
3 1 2 2 3 3 1 |
Первая строка — это количество вершин в графе, остальное направление дуг графа.
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include<iostream> #include<fstream> //библиотека для работы с файлами void transitive_closure_v_1(int **matrix, int n) { //транзитивное замыкание за четыре цикла (N^4) for (int l = 0; l < n; l++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { //если ячейка матрицы равна 1 for (int k = 0; k < n; k++) { //то запускаем цикл if (matrix[j][k] == 1) { //если ячейка матрицы равна 1 matrix[i][k] = 1; //присвоить свободной ячейке 1 } } } } } } std::ofstream out("out_matrix.txt"); //открываем файл для выходной матрицы for (int i = 0; i < n; i++) { //циклом записываем в него ответ for (int j = 0; j < n; j++) { out << matrix[i][j]; } out << '\n'; //отступ при завершении ввода ряда матрицы } out << '\n'; //делаем несколько отступов вниз в файле out << '\n'; out << '\n'; out << "Вариант: N^4"; //записываем какой вариант расчёта был выбран out.close(); //закрываем файл } void transitive_closure_v_2(int **matrix, int n) { //транзитивное замыкание за три цикла (N^3) for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (matrix[i][k] && matrix[k][j]) { matrix[i][j] = 1; } } } } std::ofstream out("out_matrix.txt"); //открываем файл для выходной матрицы for (int i = 0; i < n; i++) { //циклом записываем в него ответ for (int j = 0; j < n; j++) { out << matrix[i][j]; } out << '\n'; //отступ при завершении ввода ряда матрицы } out << '\n'; //делаем несколько отступов вниз в файле out << '\n'; out << '\n'; out << "Вариант: N^3"; //записываем какой вариант расчёта был выбран out.close(); } int main() { setlocale(LC_ALL, "Russian"); //подключаем кириллицу std::ifstream mat("input_graph.txt"); //открываем файл, в котором содержатся данные по графу int number_of_vertices_in_the_graph; //переменная для количества вершин в графе mat >> number_of_vertices_in_the_graph; //считываем верхушку файла, в которой содержится количество вершин графа int **matrix; //динамический двумерный массив под нашу матрицу matrix = new int*[number_of_vertices_in_the_graph]; for (int i = 0; i < number_of_vertices_in_the_graph; i++) { //выделение памяти под ячейки двумерного массива размерностью n matrix[i] = new int[number_of_vertices_in_the_graph]; } for (int i = 0; i < number_of_vertices_in_the_graph; i++) { //обнуление исходной матрицы for (int j = 0; j < number_of_vertices_in_the_graph; j++) { matrix[i][j] = 0; } } int v, v1; //две переменные для считывания направления дуг графа while (!mat.eof()) { //считывание из файла, пока файл не закончится mat >> v >> v1; //записываем в переменные откуда и куда идёт дуга графа matrix[v - 1][v1 - 1] = 1; //в матрицу с ячейкой под номером номера дуги - 1 записываем 1 } mat.close(); //закрываем файл из которого читали граф int select; //переменная для выбора пользователем варианта расчёта std::cout << "\nВведите номер варианта расчёта (0 - [N^4], 1 - [N^3]): "; std::cin >> select; std::cout << "\n"; switch (select){ //пользователь выбирает какой расчёт произвести case 0: transitive_closure_v_1(matrix, number_of_vertices_in_the_graph); break; //передаём в функцию нашу матрицу и размерность матрицы case 1: transitive_closure_v_2(matrix, number_of_vertices_in_the_graph); break; //передаём в функцию нашу матрицу и размерность матрицы } std::cout << "Всё готово!\n" << std::endl; //отчёт о готовности расчёта system("pause"); //ожидание нажатия клавиши return 0; } |
Таким нехитрым образом мы разобрались с темой: «Транзитивное замыкание графа»!
