ColonelNV

обход в ширину

Oct 18th, 2020 (edited)
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <list>
  2. #include <iostream>
  3. #include <queue>
  4. #include <stack>
  5. using namespace std;
  6. struct Edge {
  7.     int begin;
  8.     int end;
  9. };
  10. int main()
  11. {
  12.     system("chcp 1251");
  13.     system("cls");
  14.     queue<int> Queue;
  15.     stack<Edge> Edges;
  16.     int req;
  17.     Edge e;
  18.     int mas[10][10] = {
  19.     { 0,1,1,0,0,0,0,0,0,1 },
  20.     { 0,0,0,0,0,1,1,0,1,0 },
  21.     { 0,0,0,0,0,0,0,1,0,1 },
  22.     { 0,0,0,0,0,0,0,0,0,0 },
  23.     { 0,0,0,0,0,0,0,0,0,0 },
  24.     { 0,0,0,0,0,0,1,0,0,0 },
  25.     { 0,0,0,0,1,0,0,0,0,0 },
  26.     { 0,0,0,0,0,0,0,0,0,0 },
  27.     { 0,0,0,0,0,0,0,0,0,0 },
  28.     { 0,0,0,1,0,0,1,0,0,0 } };
  29.     int nodes[10]; // вершины графа
  30.     for (int i = 0; i < 10; i++) // исходно все вершины равны 0
  31.         nodes[i] = 0;
  32.     cout << "N = "; cin >> req;req-1;
  33.     Queue.push(0); // помещаем в очередь первую вершину
  34.     while (!Queue.empty())
  35.     {
  36.         int node = Queue.front(); // извлекаем вершину
  37.         Queue.pop();
  38.         nodes[node] = 1; // отмечаем ее как посещенную
  39.         for (int j = 0; j < 10; j++)
  40.         {
  41.             if (mas[node][j] == 1 && nodes[j] == 0)
  42.             { // если вершина смежная и не обнаружена
  43.                 Queue.push(j); // добавляем ее в очередь
  44.                 nodes[j] = 1; // отмечаем вершину как обнаруженную
  45.                 e.begin = node; e.end = j;
  46.                 Edges.push(e);
  47.                 if (node == req) break;
  48.             }
  49.         }
  50.         cout << node << endl; // выводим номер вершины
  51.     }
  52.     cout << "Путь до вершины " << req << endl;
  53.     cout << req + 1;
  54.     while (!Edges.empty()) {
  55.         e = Edges.top();
  56.         Edges.pop();
  57.         if (e.end == req) {
  58.             req = e.begin;
  59.             cout << " <- " << req ;
  60.         }
  61.     }
  62.     cin.get(); cin.get();
  63.     return 0;
  64. }
Add Comment
Please, Sign In to add comment