SHARE
TWEET

Graph-Färbung

pabloducato May 31st, 2018 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.    Program umożliwiający wygenerowanie wszystkich k-kolorowych kolorowań grafu.
  3.    Wypisuje on wszystkie możliwości w postaci ciągu liczb oznaczających kolory wierzchołków.
  4.    Kolory należą do przedziału od 0 do COLOR_NUM - 1.
  5.    Kolejność liczby w ciągu koresponduje z numerem wierzchołka.
  6. */
  7.  
  8. #include <iostream>
  9.  
  10. int main()
  11. {
  12.     const int VERT_NUM = 7; // Wprowadź ilość wierzchołków
  13.     const int COLOR_NUM = 3; // Wprowadź ilość kolorów
  14.     const int EDG_NUM = 9; // Wprowadź ilość krawędzi
  15.  
  16.     int vertices[VERT_NUM] = {0};
  17.     int edges[EDG_NUM][2];
  18.  
  19.     // Wprowadź wierzchołki kolejnych krawędzi (numeracja zaczyna się od 1)
  20.     edges[0][0] = 1, edges[0][1] = 2; // 1. krawędź
  21.     edges[1][0] = 1, edges[1][1] = 3; // 2. krawędź
  22.     edges[2][0] = 1, edges[2][1] = 6; // ...
  23.     edges[3][0] = 2, edges[3][1] = 5;
  24.     edges[4][0] = 3, edges[4][1] = 6;
  25.     edges[5][0] = 3, edges[5][1] = 4;
  26.     edges[6][0] = 4, edges[6][1] = 5;
  27.     edges[7][0] = 5, edges[7][1] = 6;
  28.     edges[8][0] = 5, edges[8][1] = 7;
  29.  
  30.     bool right = true;
  31.     int counter = 0;
  32.  
  33.     while (true)
  34.     {
  35.         for (int i = 0; i < EDG_NUM; i++)
  36.         {
  37.             if (vertices[edges[i][0] - 1] == vertices[edges[i][1] - 1])
  38.             {
  39.                 right = false;
  40.                 break;
  41.             }
  42.         }
  43.  
  44.         if (right)
  45.         {
  46.             counter++;
  47.             std::cout << "GRAF " << counter << std::endl;
  48.             for (int i = 0; i < VERT_NUM; i++)
  49.                 std::cout << vertices[i] << ' ';
  50.             std::cout << std::endl;
  51.         }
  52.  
  53.         vertices[0]++;
  54.         for (int i = 0; i < VERT_NUM - 1; i++)
  55.         {
  56.             if (vertices[i] == COLOR_NUM)
  57.             {
  58.                 vertices[i] = 0;
  59.                 vertices[i + 1]++;
  60.             }
  61.         }
  62.         if (vertices[VERT_NUM - 1] == COLOR_NUM)
  63.             break;
  64.  
  65.         right = true;
  66.     }
  67.  
  68.     std::cin.get();
  69.  
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top