Facebook
From Matyo, 2 Weeks ago, written in C++.
Embed
Download Paste or View Raw
Hits: 170
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int n = 10;
  5.  
  6. struct que
  7. {
  8.     char key;
  9.     que* next;
  10. } *First,* Last;
  11.  
  12. struct link
  13. {
  14.     char key;
  15.     link* next;
  16. } *G[n];
  17.  
  18. void init_que()
  19. {
  20.     First = NULL;
  21.     Last = NULL;
  22. };
  23.  
  24. void push_queue(char k)
  25. {
  26.     que* p = Last;  
  27.     Last = new que;  
  28.     Last->key = k;
  29.     Last->next = NULL;
  30.     if (p != NULL) p->next = Last;
  31.     if (First == NULL) //добавяне на първи елемент
  32.     {
  33.         First = Last;
  34.     }
  35. }
  36.  
  37. bool empty_queue()
  38. {
  39.     if (First == NULL)
  40.         return true;
  41.     else return false;
  42. }
  43.  
  44. char pop_queue()
  45. {
  46.    // if (First != NULL)
  47.     char z;
  48.     z = First->key;
  49.     que* p = First;  
  50.     First = First->next;
  51.     delete p;
  52.     return z;
  53. }
  54.  
  55.  
  56.  
  57. //инициализация на граф
  58. void init(link* gr[n])
  59. {
  60.     for (int i = 0; i < n; i++)  
  61.         gr[i] = NULL;
  62. }
  63.  
  64. // търсене на връх в графа
  65. int search_node(link* gr[n], char c)
  66. {
  67.     int flag = 0;
  68.     for (int i = 0; i < n; i++)
  69.         if (gr[i]) //проверка, дали даден връх съществува  
  70.             if (gr[i]->key==c)
  71.                 flag = 1;  
  72.     return flag;
  73. }
  74.  
  75. // търсене на дъга в графа
  76. int search_arc(link* gr[5], char c1, char c2)
  77. //c1 и c2 - ключовите стойности на възлите, които
  78. //свързва търсената дъга
  79. {
  80.     int flag = 0;
  81.     if (search_node(gr, c1) && search_node(gr, c2))
  82.     {
  83.         int i = 0;
  84.         while (gr[i]->key != c1)
  85.             i++;  
  86.         link* p = gr[i];
  87.         while (p->key != c2 && p->next != NULL)
  88.             p = p->next;  
  89.         if (p->key == c2)
  90.             flag = 1;
  91.     }
  92.     return flag;
  93. }
  94.  
  95. //включване на връх в графа
  96. void add_node(link* gr[n], char c)  // c е добавената стойност
  97. {
  98.     if (search_node(gr, c))
  99.     {
  100.         cout << "nВърхът вече съществува!n";
  101.     }
  102.     else
  103.     {
  104.         int j = 0;
  105.         while (gr[j] && (j < n))
  106.             j++;  
  107.         if (gr[j] == NULL)
  108.         {
  109.             gr[j] = new link;  // създаване на нов връх
  110.             gr[j]->key = c;   // установяване на ключовата стойност
  111.             gr[j]->next = NULL; //и указателя
  112.         }
  113.         else
  114.         {
  115.             cout << "nПрепълване на структурата!n";
  116.         }
  117.     }
  118. }
  119.  
  120. //включване на дъга
  121. void add_arc(link* gr[n], char c1, char c2)
  122. {
  123.     int i = 0;  link* p;
  124.     if (search_arc(gr, c1, c2))
  125.     {
  126.         cout << "nДъгата вече съществува!";
  127.     }
  128.     else
  129.     {
  130.         if (!(search_node(gr, c1)))
  131.             add_node(gr, c1);  
  132.         if (!(search_node(gr, c2)))
  133.             add_node(gr, c2);  
  134.         while (gr[i]->key != c1)
  135.             i++;
  136.         p = new link;  // създаване на нов елемент
  137.         p->key = c2;   // в списъка на съседство
  138.         p->next = gr[i]->next;  
  139.         gr[i]->next = p;
  140.     }
  141. }
  142.  
  143. //премахване на връх от графа
  144. void del_node(link* gr[n], char c)
  145. {
  146.     if (search_node(gr, c))
  147.     {
  148.         int i = 0;
  149.         while (gr[i]->key != c)  //търсене на върха който се изтрива;
  150.             i++;  
  151.         link* p;
  152.         link *q=gr[i];
  153.         while (gr[i] != NULL)
  154.         {
  155.             p = gr[i];
  156.             gr[i] = p->next;
  157.             delete p;
  158.         }
  159.         //изтриване на върха и на дъгите, излизащи от него  
  160.         for (i=0;i<n;i++)
  161.             if (gr[i])
  162.             {
  163.                 p = gr[i];
  164.                     while ((p->key != c) && (p->next != NULL))
  165.                     {
  166.                         q = p;
  167.                         p = p->next;
  168.                     }
  169.                     if (p->key == c) // изтриване на дъгите влизащи във върха
  170.                     {
  171.                         q->next = p->next;
  172.                         delete p;
  173.                     }
  174.             }
  175.     }
  176.     else { cout << "В графа няма такъв връх!"; }
  177. }
  178.  
  179. //премахване на дъга от графа
  180. void del_arc(link* gr[n], char c1, char c2)
  181. {
  182.     if (search_arc(gr, c1, c2))
  183.     {
  184.         int i = 0;
  185.         while (gr[i]->key != c1)
  186.             i++;
  187.         link* p = gr[i], * q=gr[i];  
  188.         while (p->key != c2)
  189.         {
  190.             q = p;
  191.             p = p->next;
  192.         }  
  193.         q->next = p->next;
  194.         delete p; //премахване на върха от списъка на съседство
  195.     }
  196.     else { cout << "nВ графа няма такава дъга!"; }
  197. }
  198.  
  199. // функция която връща индекса на връх к от масива със съседите.
  200. int convert(link* gr[n], char k)
  201. {
  202.     bool flag = false;
  203.     int pos=-1;
  204.     for (int i = 0; i < n; i++)
  205.     {
  206.         if (gr[i]->key == k)
  207.         {
  208.             flag = true;
  209.             pos = i;
  210.             break;
  211.         }
  212.     }
  213.     if (flag) return pos;
  214.     else return -1;
  215. }
  216.  
  217. void bfs(link* gr[n], char k)
  218. {
  219.     int m[n]; // масив за регистриране на обходените върхове
  220.    // memset(m, 0, 10);
  221.     for (int i = 0; i < n; i++) m[i] = 0;
  222.     init_que(); //инициализация на помощната опашка  
  223.     push_queue(k); //поместване в опашка на първия елемент  
  224.     while (!empty_queue()) //докато опашката не е празна
  225.     {
  226.        // cout << "------------------";
  227.         char s = pop_queue(); //извличане на поредния елемент от опашката
  228.         int j = convert(gr,s); //функция, която връща индекса на елемента на масива от списъците на съседство, чиято стойност е k.
  229.         if (m[j] == 0) //Възелът не е посетен
  230.         {
  231.             m[j] = 1;
  232.             cout << s << " ";//регистриране и визуализация на възела
  233.             //cout << "---------";
  234.         }  
  235.         for (link* t = gr[j]; t != NULL; t = t->next)
  236.         {
  237.             int h = convert(gr, t->key);
  238.             if (m[h] == 0)  // възела не е посетен
  239.                 push_queue(t->key); // включване на възела в опашката
  240.         }
  241.     }
  242. }
  243.  
  244. void dfs(link* gr[n], char k, int m[])
  245. {
  246.     cout << k <<" ";
  247.     int j = convert(gr, k);
  248.     m[j] = 1;
  249.     for (link* t = gr[j]->next; t != NULL; t = t->next)
  250.     {
  251.         int h = convert(gr, t->key);
  252.         if (m[h]==0)
  253.             dfs(gr, t->key, m);
  254.     }
  255. }
  256.  
  257. int main()
  258. {
  259.  
  260.     link* graf[n];
  261.     init(graf);
  262.     char c1, c2;
  263.  
  264.     int br;
  265.     cout << "Vavedi kolko varhove na grafa iskash da dobavish" << endl;
  266.     cin >> br;
  267.     for (int j=0; j < br; j++)
  268.     {
  269.         cout << "Vavedi vrah na grafa c= ";
  270.         cin >> c1;
  271.         add_node(graf, c1);
  272.     }
  273.  
  274.     cout << "Vavedi kolko dagi na grafa iskash da dobavish" << endl;
  275.     cin >> br;
  276.     for (int j=0; j < br; j++)
  277.     {
  278.         cout << "Na4alen vrah na dagata ";
  279.         cin >> c1;
  280.         cout << "Kraen vrah na dagata ";
  281.         cin >> c2;
  282.         add_arc(graf, c1, c2);
  283.     }
  284.  
  285.     cout << "Vavedi kolko dagi na grafa iskash da iztriesh" << endl;
  286.     cin >> br;
  287.     for (int j=0; j < br; j++)
  288.     {
  289.         cout << "Na4alen vrah na dagata ";
  290.         cin >> c1;
  291.         cout << "Kraen vrah na dagata ";
  292.         cin >> c2;
  293.         del_arc(graf, c1, c2);
  294.     }
  295.  
  296.     cout << "Vavedi kolko varhove na grafa iskash da iztriesh" << endl;
  297.     cin >> br;
  298.     for (int j=0; j < br; j++)
  299.     {
  300.         cout << "Iztrivane na vrah";
  301.         cin >> c1;
  302.         del_node(graf, c1);
  303.     }
  304.  
  305.     cout << "Izberi na4alen vrah za obhojdaneto"<<endl;
  306.     cin >> c1;
  307.     //bfs(graf, c1);
  308.  
  309.     int m[n]; // масив за регистриране на обходените върхове
  310.     for (int i = 0; i < n; i++)
  311.         m[i] = 0;
  312.     dfs(graf, c1, m);
  313. }