ColonelNV

graph

Nov 30th, 2020
363
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. struct Edge
  5. {
  6.     int begin;
  7.     int end;
  8. };
  9. int mas[10][10] =
  10. {
  11. { 0, 1, 1, 0, 0, 0, 0, 0, 0, 1 },
  12. { 0, 0, 0, 0, 0, 1, 1, 0, 1, 0 },
  13. { 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 },
  14. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
  15. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
  16. { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
  17. { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
  18. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
  19. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
  20. { 0, 0, 0, 1, 0, 0, 1, 0, 0, 0 },
  21. };
  22. int nodes[10];
  23. stack <int> Stack;
  24. stack <Edge> Edges;
  25. Edge e;
  26.  
  27. void VGLrec(int Start, int End)
  28. {
  29.     int r;
  30.     cout << Start + 1 << " ";
  31.     nodes[Start] = 1;
  32.     for (r = 0; r < End; r++)
  33.         if ((mas[Start][r] != 0) && (nodes[r] == 0))
  34.             VGLrec(r, End);
  35. }
  36.  
  37. void VGL(int Start, int End)
  38. {
  39.     int n=0;
  40.     Stack.push(Start);
  41.     cout << "Путь обхода:" << endl;
  42.     while (!Stack.empty())
  43.     { //пока стек не пуст
  44.         int node = Stack.top(); // извлекаем вершину
  45.         Stack.pop();
  46.         if (nodes[node] == 2) continue;
  47.         nodes[node] = 2; // отмечаем ее как посещенную
  48.         for (int j = 6; j >= 0; j--)
  49.         { //проверяем для нее все смежные варианты
  50.             if (mas[node][j] == 1 && nodes[j] != 2)
  51.             { // если вершина смежная и не обнаружена
  52.                 Stack.push(j); // добавляем ее в стек
  53.                 nodes[j] = 1; // отмечаем вершину как обнаруженную
  54.                 e.begin = node; e.end = j;
  55.  
  56.                 Edges.push(e);
  57.                 if (node == End) break;
  58.             }
  59.         }
  60.         cout << node + 1 << " ";
  61.     }
  62.     cout << endl;
  63.     cout << "Путь до вершины " << End + 1 << endl;
  64.     cout << End + 1;
  65.     while (!Edges.empty())
  66.     {
  67.         e = Edges.top();
  68.         Edges.pop();
  69.         if (e.end == End)
  70.         {
  71.             End = e.begin;
  72.             cout << " <- " << End + 1;
  73.             n++;
  74.         }
  75.     }
  76.     cout << endl;
  77.     cout << "Количество шагов: " << n << endl;
  78. }
  79.  
  80. void VSH(int Start, int End)
  81. {
  82.    
  83.     Stack.push(Start);
  84.     int n=0;
  85.     cout << "Путь обхода:" << endl;
  86.     while (!Stack.empty())
  87.     {
  88.         int node = Stack.top(); // извлекаем вершину
  89.         Stack.pop();
  90.         nodes[node] = 2; // отмечаем ее как посещенную
  91.         for (int j = 0; j < 7; j++)
  92.         {
  93.             if (mas[node][j] == 1 && nodes[j] == 0)
  94.             { // если вершина смежная и не обнаружена
  95.                 Stack.push(j); // добавляем ее в стек
  96.                 nodes[j] = 1; // отмечаем вершину как обнаруженную
  97.                 e.begin = node; e.end = j;
  98.                 Edges.push(e);
  99.                 if (node == End) break;
  100.                 n++;
  101.             }
  102.         }
  103.         cout << node + 1 << " ";
  104.     }
  105.     cout << endl;
  106.     cout << "Путь до вершины " << End + 1 << endl;
  107.     cout << End + 1;
  108.     while (!Edges.empty())
  109.     {
  110.  
  111.         e = Edges.top();
  112.         Edges.pop();
  113.         if (e.end == End)
  114.         {
  115.             End = e.begin;
  116.             cout << " <- " << End + 1;
  117.         }
  118.     }
  119.     cout << endl;
  120.     cout << "Количество шагов: " << n << endl;
  121. }
  122.  
  123. int main()
  124. {
  125.     setlocale(LC_ALL, "rus");
  126.     for (int i = 0; i < 7; i++) // исходно все вершины равны 0
  127.         nodes[i] = 0;
  128.     int F;
  129.     int Start, End;
  130.     cout << "Введите начальную вершину: ";
  131.     cin >> Start; Start--;
  132.     cout << "Введите целевую вершину: ";
  133.     cin >> End; End--;
  134.     cout << "МЕНЮ:\n";
  135.     cout << "1) В ширину\n";
  136.     cout << "2) В глубиину\n";
  137.     cout << "3) В глубину с рекурсией\n";
  138.     cout << "4.Выход\n\n";
  139.     cin >> F;
  140.     cout << endl;
  141.     switch (F)
  142.     {
  143.     case 1:
  144.         VSH(Start, End);
  145.         break;
  146.     case 2:
  147.         VGL(Start, End);
  148.         break;
  149.     case 3:
  150.         cout << "Путь обхода:" << endl;
  151.         VGLrec(Start, End);
  152.         cout << End + 1 << endl;
  153.         break;
  154.     case 4:
  155.         exit(0);
  156.         break;
  157.     default:
  158.         cout << "Неверный пункт меню!\n";
  159.         return F;
  160.         break;
  161.     }
  162.     return 0;
  163. }
RAW Paste Data