Toxotsist

Граф

Nov 27th, 2021
932
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. using namespace std;
  5.  
  6. struct pr {
  7.     int x;
  8.     bool marked = false;
  9.     pr(int i) {
  10.         x = i;
  11.     }
  12. };
  13.  
  14. typedef pr Pair;
  15.  
  16. struct node {
  17.     int i = NULL;
  18.     vector <int> edges;
  19.     node* nextVertex;
  20.     node(int n) {
  21.         i = n;
  22.         nextVertex = NULL;
  23.     }
  24. };
  25.  
  26. typedef node Node;
  27.  
  28. class Graph {
  29.     Node* head;
  30.     deque<Pair> visited;
  31.     int N;
  32. public:
  33.     Graph(int t){
  34.         this->N = t;
  35.     }
  36.     void addEdge(int, int, bool);
  37.     void addVertex(int);
  38.     node* existVertex(int);
  39.     void print();
  40.     bool eiler();
  41.     void get_tree();
  42.     node* nextUp(node* i);
  43. };
  44.  
  45. node* Graph::existVertex(int i) {
  46.     node* cur = this->head;
  47.     while (cur != NULL) {
  48.         if (cur->i == i) {
  49.             return cur;
  50.             break;
  51.         }
  52.         cur = cur->nextVertex;
  53.     }
  54.     return 0;
  55. }
  56.  
  57. void Graph::addEdge(int i, int j, bool status) {
  58.     if (this->head == NULL) {
  59.         this->head = new node(i);
  60.         this->head->edges.push_back(j);
  61.         node* cur = this->head;
  62.         if (status == true) {
  63.             cur->nextVertex = new node(j);
  64.             cur->nextVertex->edges.push_back(i);
  65.         }
  66.     }
  67.     else if (existVertex(i) != NULL) {
  68.         node* cur = existVertex(i);
  69.         cur->edges.push_back(j);
  70.         if (existVertex(j) == NULL) {
  71.             while (cur->nextVertex != NULL) cur = cur->nextVertex;
  72.             cur->nextVertex = new node(j);
  73.         }
  74.         if (status == true) {
  75.             cur->nextVertex->edges.push_back(i);
  76.         }
  77.     }
  78.     else {
  79.         node* cur = this->head;
  80.         while (cur->nextVertex != NULL) cur = cur->nextVertex;
  81.         cur->nextVertex = new node(i); //cur->nextVertex->edges.push_back(pr(j,w));
  82.         if (existVertex(j) == NULL) {
  83.             cur->nextVertex = new node(j);
  84.         }
  85.         else {
  86.             node* buf = this->head; while (buf->i != j) buf = buf->nextVertex;
  87.             buf->edges.push_back(i);
  88.         }
  89.         if (status == true) {
  90.             cur->nextVertex->edges.push_back(j);
  91.         }
  92.     }
  93. }
  94.  
  95. void Graph::addVertex(int i) {
  96.     if (existVertex(i) == NULL) {
  97.         node* cur = this->head;
  98.         while (cur->nextVertex != NULL) cur = cur->nextVertex;
  99.         cur->nextVertex = new node(i);
  100.     }
  101. }
  102.  
  103. void Graph::print() {
  104.     node* cur = this->head;
  105.     while (cur != NULL) {
  106.         std::cout << cur->i << " -> ";
  107.         if (cur->edges.size() == 1) {
  108.             printf("%d", *cur->edges.begin());
  109.         }
  110.         else {
  111.             auto it = cur->edges.begin();
  112.             auto end = cur->edges.end();
  113.             while (it != end) {
  114.                 printf("%d ", *it);
  115.                 it++;
  116.             }
  117.         }
  118.         cur = cur->nextVertex;
  119.         printf("\n");
  120.     }
  121. }
  122.  
  123. bool Graph::eiler() {
  124.     node* cur = this->head;
  125.     int count = 0;
  126.     while (cur != NULL) {
  127.         if (cur->edges.size() != 0) {
  128.             if (cur->edges.size() % 2 == 1) count++;
  129.         }
  130.         cur = cur->nextVertex;
  131.     }
  132.     if (count > 2) return false;
  133.     else return true;
  134. }
  135.  
  136. node* Graph::nextUp(node* i) {
  137.     node* buff = i; node* b = this->head;
  138.     for (int i = 0; i < this->visited.size(); i++) {
  139.         if (visited[i].x == buff->i) {
  140.             this->visited[i].marked = true;
  141.             //if (buff->edges.size() > 2) this->visited[i].marked = false;
  142.             break;
  143.         }
  144.     }
  145.     cout <<  " -> " << buff->i;
  146.     for (int i = 0; i < buff->edges.size(); i++) {
  147.         while (b->i != buff->edges.at(i)) b = b->nextVertex;
  148.         for (int i = 0; i < visited.size(); i++) {
  149.             if (visited[i].x == b->i && visited[i].marked == false) return nextUp(b);
  150.         }
  151.     }
  152. }
  153.  
  154. void Graph::get_tree() {
  155.     node* cur = this->head;
  156.     while (cur != NULL) {
  157.         visited.push_back(pr(cur->i));
  158.         cur = cur->nextVertex;
  159.     }
  160.     cur = this->head;
  161.     nextUp(cur);
  162.     for (int i = 0; i < visited.size(); i++) {
  163.         if (visited[i].marked == false) {
  164.             cur = this->head;
  165.             this->visited[i].marked = true;
  166.             while (cur->i != visited[i].x) cur = cur->nextVertex;
  167.             cout << " -> " << cur->edges.at(0);
  168.             nextUp(cur);
  169.         }
  170.     }
  171. }
  172.  
  173. int main() {
  174.     setlocale(0, "");
  175.     Graph G(10); int i = 0, j = 0;
  176.     cout << "\nЧтобы добавить ребро, введите 1.\nЧтобы вывести граф, введите 2.\nЧтобы определить эйлеров цикл, нажмите 3.\nЧтобы найти эйлеров путь, нажмите 4.\n";
  177.     int n = -1; int s = 0; node* tmp;
  178.     node* tree = NULL;
  179.     while (n != 0) {
  180.         cin >> n;
  181.         switch (n) {
  182.         case 1:
  183.             cin >> i; cin >> j;
  184.             G.addEdge(i, j, true);
  185.             i = 0, j = 0;
  186.             break;
  187.         case 2:
  188.             G.print();
  189.             printf("\n");
  190.             break;
  191.         case 3:
  192.             cout << "Граф эйлеров? ->" << G.eiler() << endl;
  193.             break;
  194.         case 4:
  195.             G.get_tree();
  196.             break;
  197.         }
  198.     }
  199.     return 0;
  200. }
RAW Paste Data