Advertisement
baadgeorge

Untitled

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