Advertisement
baadgeorge

Untitled

Apr 9th, 2021
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 10.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. using namespace std;
  5.  
  6. const int inf = INT32_MAX; // бесконечно большая величина
  7. const int null = INT32_MIN; // бесконечно маленькая величина
  8.  
  9. const int n = 15; // кол-во вершин графа
  10.  
  11. // структура, описывающая ребро графа
  12. struct _edge
  13. {
  14.     int cost;
  15.     int parent1;
  16.     int parent2;
  17. };
  18.  
  19. int leader[n] = { 0 }; // массив корней поддеревьев
  20.  
  21. // заполнение ячейки массива корней поддеревьев начальным значением
  22. void make_set(int v)
  23. {
  24.     leader[v] = v;
  25. }
  26.  
  27. // функция, определяющая принадлежность вершины к поддереву
  28. int find_set(int v)
  29. {
  30.     if (v == leader[v])
  31.         return v;
  32.     return leader[v] = find_set(leader[v]); // возвращает корень поддерева
  33. }
  34.  
  35. // функция объединения поддеревьев
  36. int union_sets(int a, int b)
  37. {
  38.     a = find_set(a);
  39.     b = find_set(b);
  40.     if (a != b)
  41.     {
  42.         leader[b] = a;
  43.         return 1;
  44.     }
  45.     return 0;
  46. }
  47.  
  48. //алгоритм Флойда-Уоршелла поиска кратчайших путей
  49. void Floyd_Warshall(int matrix[][n], int(*shortest)[n][n][n + 1], int(*pred)[n][n][n + 1])
  50. {
  51.     // заполняем матрицу кратчайших путей и матрицу предшествующих вершин начальными значениями
  52.     for (int u = 0; u < n; u++)
  53.         for (int v = 0; v < n; v++)
  54.         {
  55.             (*shortest)[u][v][0] = matrix[u][v];
  56.             if ((matrix[u][v] == inf) || (matrix[u][v] == 0)) (*pred)[u][v][0] = NULL;
  57.             else (*pred)[u][v][0] = u;
  58.         }
  59.  
  60.     for (int x = 1; x < n + 1; x++)
  61.     {
  62.         // перезаписываем массив крачайших путей с х-1 итерации на х
  63.         for (int i = 0; i < n; i++)
  64.             for (int j = 0; j < n; j++)
  65.                 (*shortest)[i][j][x] = (*shortest)[i][j][x - 1];
  66.  
  67.         // проходим по всем элементам матрицы на х-ой итерации
  68.         for (int u = 0; u < n; u++)
  69.             for (int v = 0; v < n; v++)
  70.             {
  71.                 // если найден более короткий путь, то записываем его в массив shortest
  72.                 if (((*shortest)[u][v][x] > (((*shortest)[u][x - 1][x - 1] + (*shortest)[x - 1][v][x - 1]))) && ((((*shortest)[u][x - 1][x - 1]) != inf) && (((*shortest)[x - 1][v][x - 1]) != inf)))
  73.                 {
  74.  
  75.                     (*shortest)[u][v][x] = (*shortest)[u][x - 1][x - 1] + (*shortest)[x - 1][v][x - 1];
  76.                     (*pred)[u][v][x] = (*pred)[x - 1][v][x - 1];
  77.                 }
  78.                 // если более короткий путь не найден, то записываем значение из массива предыдущей итерации в массив shortest и pred текущей итерации
  79.                 else
  80.                 {
  81.                     (*shortest)[u][v][x] = (*shortest)[u][v][x - 1];
  82.                     (*pred)[u][v][x] = (*pred)[u][v][x - 1];
  83.                 }
  84.             }
  85.     }
  86. }
  87.  
  88. // функция форматированного вывода матрицы shortest кратчайших путей
  89. void outputFW(int shortest[n][n][n + 1], int pred[n][n][n + 1])
  90. {
  91.     for (int x = 0; x < n + 1; x++)
  92.     {
  93.         cout << "\n****************************************************\n";
  94.         cout << "\nx = " << x << "\n";
  95.  
  96.         cout << "\nSHORTEST: \n\n";
  97.         for (int u = 0; u < n; u++)
  98.         {
  99.             for (int v = 0; v < n; v++)
  100.             {
  101.                 if (shortest[u][v][x] == inf) cout << setw(8) << "inf" << " ";
  102.                 else cout << setw(8) << shortest[u][v][x] << " ";
  103.             }
  104.             cout << "\n";
  105.         }
  106.  
  107.         cout << "\nPRED: \n\n";
  108.         for (int u = 0; u < n; u++)
  109.         {
  110.             for (int v = 0; v < n; v++)
  111.             {
  112.                 if (pred[u][v][x] == null) cout << setw(8) << "null" << " ";
  113.                 else cout << setw(8) << pred[u][v][x] << " ";
  114.             }
  115.             cout << "\n";
  116.         }
  117.     }
  118.     cout << "\n****************************************************\n\n";
  119. }
  120.  
  121. // форматированный вывод матрицы смежности графа
  122. void outputMatrix(int matrix[][n])
  123. {
  124.     for (int u = 0; u < n; u++)
  125.     {
  126.         for (int v = 0; v < n; v++)
  127.         {
  128.             if (matrix[u][v] == inf) cout << setw(8) << "inf" << " ";
  129.             else cout << setw(8) << matrix[u][v] << " ";
  130.         }
  131.         cout << "\n";
  132.     }
  133. }
  134.  
  135. // функция перевода графа из ориентированного в неориентированный и подсчета кол-ва ребер
  136. void makeGraphUnoriented(int(*matrix)[n][n], int* RealEdgeCount)
  137. {
  138.     for (int u = 0; u < n; u++)
  139.     {
  140.         for (int v = u + 1; v < n; v++)
  141.         {
  142.             if (((*matrix)[u][v] == inf) && ((*matrix)[v][u] != inf))
  143.             {
  144.                 (*matrix)[u][v] = (*matrix)[v][u];
  145.                 (*RealEdgeCount)++;
  146.             }
  147.                
  148.             if (((*matrix)[v][u] == inf) && ((*matrix)[u][v] != inf))
  149.             {
  150.                 (*matrix)[v][u] = (*matrix)[u][v];
  151.                 (*RealEdgeCount)++;
  152.             }
  153.                
  154.         }
  155.     }
  156. }
  157.  
  158. // сортировка Шелла
  159. void ShellSort(_edge **edge, int RealEdgeCount)
  160. {
  161.     int h = 0;
  162.  
  163.     while (h < RealEdgeCount / 3)
  164.     {
  165.         h = 3 * h + 1;
  166.     }
  167.  
  168.     for (h; h > 0; h = (h - 1) / 3)
  169.     {
  170.         for (int i = h; i < RealEdgeCount; i++)
  171.         {
  172.             int j = i;
  173.             _edge tmp = (*edge)[i];
  174.  
  175.             for (j = i; j >= h && (*edge)[j - h].cost > tmp.cost; j -= h)
  176.             {
  177.                 (*edge)[j] = (*edge)[j - h];
  178.  
  179.             }
  180.             (*edge)[j] = tmp;
  181.         }
  182.     }
  183.  
  184.     return;
  185. }
  186.  
  187. // функция алгоритма Краскала построения остовного дерева графа
  188. void graphKruskalAlgorithm(int matrix [n][n], int RealEdgeCount)
  189. {
  190.     int newMatrix[n][n];
  191.  
  192.     for (int u = 0; u < n; u++)
  193.         for (int v = 0; v < n; v++)
  194.             if (u == v) newMatrix[u][v] = 0;
  195.             else newMatrix[u][v] = inf;
  196.  
  197.     //outputMatrix(newMatrix);
  198.  
  199.     int i = 0;
  200.  
  201.     cout << "\n\nАлгоритм Краскала\n";
  202.  
  203.     _edge* edge = new _edge[RealEdgeCount];
  204.  
  205.     for (int u = 0; u < n; u++)
  206.     {
  207.         for (int v = u + 1; v < n; v++)
  208.         {
  209.             if(matrix[u][v]!=inf)
  210.             {
  211.                 edge[i].cost = matrix[u][v];
  212.                 edge[i].parent1 = u;
  213.                 edge[i].parent2 = v;
  214.                 i++;
  215.             }
  216.            
  217.         }
  218.     }
  219.     cout << "\nНеотсортированные ребра: \n";
  220.     for (int k = 0; k < RealEdgeCount; k++)
  221.         cout << "\tРебро " << k + 1 << ": Cost = " << edge[k].cost << ", 1-я вершина = " << edge[k].parent1 + 1 << ", 2-я вершина = " << edge[k].parent2 + 1 << "\n";
  222.     cout << "\n";
  223.  
  224.     ShellSort(&edge, RealEdgeCount);
  225.  
  226.     cout << "\nОтсортированные ребра: \n";
  227.     for (int k = 0; k < RealEdgeCount; k++)
  228.         cout << "\tРебро " << k + 1 << ": Вес = " << edge[k].cost << ", 1-я вершина = " << edge[k].parent1 + 1 << ", 2-я вершина = " << edge[k].parent2 + 1 << "\n";
  229.     cout << "\n";
  230.  
  231.     // заполнение массива корней поддеревьев начальными значениями
  232.     for (i = 0; i < n; i++)
  233.     {
  234.         make_set(i);
  235.     }
  236.  
  237.     // заполнение матрицы смежности для остовного дерева графа
  238.     for (i = 0; i < RealEdgeCount; i++)
  239.     {
  240.         if (edge[i].cost == inf) continue;
  241.         if (union_sets(edge[i].parent1, edge[i].parent2) == 1)
  242.         {
  243.             newMatrix[edge[i].parent1][edge[i].parent2] = edge[i].cost;
  244.             newMatrix[edge[i].parent2][edge[i].parent1] = edge[i].cost;
  245.         }
  246.     }
  247.  
  248.     // копирование элементов полученной матрицы в исходную
  249.     for (int u = 0; u < n; u++)
  250.         for (int v = 0; v < n; v++)
  251.             matrix[u][v] = newMatrix[u][v];
  252. }
  253.  
  254. int main()
  255. {
  256.  
  257.     setlocale(LC_ALL, "RUS");
  258.     system("color F0");
  259.  
  260.     int shortest[n][n][n + 1] = { 0 }; // массив матриц кратчайших путей найденных на каждой из итераций
  261.     int pred[n][n][n + 1] = { 0 }; // массив матриц предшествующих вершин найденных на каждой из итераций
  262.  
  263.     int RealEdgeCount = 0; // счетчик кол-ва ребер
  264.    
  265.     int matrix[n][n] =
  266.     {
  267.     {   0,  -1, inf,   2, inf, inf, inf, inf, inf, inf,  8, inf, inf, inf, inf },
  268.     { inf,   0, inf,   3, inf,  10, inf, inf, inf, inf, inf, inf, inf, inf, inf },
  269.     { inf,   4,   0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
  270.     { inf, inf, inf,   0, inf, inf,  13, inf, inf, inf,  -7, inf, inf, inf, inf },
  271.     { inf, inf, inf, inf,   0, inf, inf,   3, inf,  11, inf, inf, inf, inf, inf },
  272.     { inf, inf, inf, inf, inf,   0, inf, inf,  18, inf, inf, inf, inf, inf, inf },
  273.     { inf, inf, inf, inf, inf, inf,   0, inf, inf,  15, inf, inf, inf, inf, inf },
  274.     { inf, inf, inf, inf, inf,  -8, inf,  0, inf, inf, inf, inf, inf, inf, inf },
  275.     { inf, inf, inf, inf, inf, inf, inf, inf,   0, inf, inf, inf, inf, inf, inf },
  276.     { inf, inf, inf, inf, inf, inf, inf, inf,  19,   0, inf, inf, inf, inf, inf },
  277.     { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,   0, inf, inf,   2,  11 },
  278.     { inf, inf, inf, inf,  16, inf, inf, inf, inf, inf, inf,   0,  12, inf, inf },
  279.     { inf, inf, inf, inf, inf, inf,  17, inf, inf, inf, inf, inf,   0, inf, inf },
  280.     { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,   0,   9 },
  281.     { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,   1,  -7, inf,   0 }
  282.     };
  283.  
  284.     //алгоритм Флойда-Уоршелла поиска кратчайших путей
  285.     Floyd_Warshall(matrix, &shortest, &pred);
  286.  
  287.     // форматированный вывод массивов матриц shortest и pred
  288.     outputFW(shortest, pred);
  289.  
  290.     cout << "\nДелаем граф неориентированным...\n\n";
  291.  
  292.     // функция перевода графа из ориентированного в неориентированный и подсчета кол-ва ребер
  293.     makeGraphUnoriented(&matrix, &RealEdgeCount);
  294.  
  295.     cout << "\nПреобразованная матрица графа: \n\n";
  296.  
  297.     // функция форматированного вывода матрицы смежности графа
  298.     outputMatrix(matrix);
  299.  
  300.     // функция алгоритма Краскала построения остовного дерева графа
  301.     graphKruskalAlgorithm(matrix, RealEdgeCount);
  302.  
  303.     cout << "\nРезультирующая матрица графа: \n\n";
  304.  
  305.     outputMatrix(matrix);
  306.  
  307.     cout << "\n";
  308.  
  309.     system("pause");
  310. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement