Раскрасить вершины графа, чтобы смежные вершины были окрашены в различные цвета

//Visual Studio 2015
//Последовательная раскраска вершин графа при помощи
//обхода графа в глубину.        
//Граф представлен структурой Вирта.
#include <iostream>
#include <windows.h>
 
using namespace std;
 
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.
 
                        //Описание типа заголовочного узла.
typedef struct L
{
 int Key; //Имя заголовочного узла.
 int Color; //Цвет раскраски.
 int Count; //Количество предшественников.
 Boolean Flag; //Флаг посещения узла при обходе.
 Tref Trail; //Указатель на список смежности.
 Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
};
 
//Описание типа дугового узла.
typedef struct T
{
 Lref Id;
 Tref Next;
};
 
class Spisok
{
private:
 Lref Head; //Указатель на голову списка заголовочных узлов.
 Lref Tail; //Указатель на фиктивный элемент 
            // в конце списка заголовочных узлов.
 int MSet[256]; //Вспомогательное множество, содер- 
                //жащее 0,1,2...,n.
 void SearchGraph(int, Lref *);
public:
 Spisok() {//Инициализация списка заголовочных узлов.
  Head = Tail = new (L);
 }
 Lref GetHead() { return Head; }
 Lref GetTail() { return Tail; }
 void MakeGraph();
 void PrintGraph();
 void Color(Lref, int);
 void Postr(int);
};
 
void Spisok::Postr(int n)
//Построение вспомогательного множества MSet.
{
 for (int i = 0; i<256; i++)
  MSet[i] = (i <= n) ? 1 : 0;
}
 
void Spisok::SearchGraph(int w, Lref *h)
//Функция возвращает указатель на заголовочный узел 
//с ключом w в графе, заданном структурой Вирта с указателем Head. 
{
 *h = Head; (*Tail).Key = w;
 while ((**h).Key != w) *h = (**h).Next;
 if (*h == Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
 {
  Tail = new (L); (**h).Count = 0;
  (**h).Trail = NULL; (**h).Next = Tail;
 }
}
 
void Spisok::MakeGraph()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
 int x, y;
 Lref p, q; //Рабочие указатели.
 Tref t, r; //Рабочие указатели.
 Boolean Res; //Флаг наличия дуги.
 cout << "Вводите начальную вершину дуги: ";
 cin >> x;
 while (x != 0)
 {
  cout << "Вводите конечную вершину дуги: "; cin >> y;
  //Определим, существует ли в графе дуга (x,y)?
  SearchGraph(x, &p); SearchGraph(y, &q);
  r = (*p).Trail; Res = FALSE;
  while ((r != NULL) && (!Res))
   if ((*r).Id == q) Res = TRUE;
   else r = (*r).Next;
   if (!Res) //Если дуга отсутствует, то поместим её в граф.
   {
    t = new (T); (*t).Id = q;
    (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++;
   }
   cout << "Вводите начальную вершину дуги (0 - выход): "; cin >> x;
 }
}
 
void Spisok::PrintGraph()
//Вывод структуры Вирта, заданной указателем 
//Head и соответствующей ориентированному графу.
{
 Lref p; //Рабочий указатель.
 Tref q; //Рабочий указатель.
 
 p = Head;
 while (p != Tail)
 {
  cout << (*p).Key << "("; q = (*p).Trail;
  while (q != NULL)
  {
   cout << (*(*q).Id).Key; q = (*q).Next;
  }
  cout << ")"; p = (*p).Next; cout << " ";
 }
}
 
void Spisok::Color(Lref r, int n)
//Последовательная раскраска графа при помощи
//рекурсивного обхода графа в глубину.
//r - указатель на структуру Вирта.
//MSet - глобальное множество.
//n    - количество вершин в графе.
{
 Tref t, t1;
 int i;         //Параметр цикла.
 Boolean Fl;
 
 t = r->Trail; r->Flag = FALSE;
 //Сейчас мы находимся в вершине r->Key.
 //Исключим цвета всех вершин, смежных вершине
 //r->Key, из множества MSet.
 t1 = t;
 while (t1 != NULL)
 {
  MSet[t1->Id->Color] = 0; t1 = t1->Next;
 }
 //Выбор цвета вершины: это "первый" элемент множества MSet.
 Fl = TRUE; i = 1;
 while (Fl)
  if (MSet[i]) Fl = FALSE; else  i++;
 r->Color = i;   //Цвет присвоен!
 cout << "(" << r->Key << "," << r->Color << ") ";
 //Восстановление вспомогательного множества MSet.
 for (i = 0; i<256; MSet[i++] = 0);
 for (i = 0; i <= n; MSet[i++] = 1);
 // ------------- 
 while (t != NULL)
 {
  if (t->Id->Flag) Color(t->Id, n);
  t = t->Next;
 }
}
 
int main() {
 
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 //Если нет русских букв при вводе, поставьте шрифт Lucida Console в свойствах окна консоли
 
 Spisok A;
 Lref t; //Рабочий указатель для перемещения 
         // по списку заголовочных звеньев.
 int n = 0; //Количество вершин в графе.
 
            //Построение графа и вывод его структуры Вирта.
 A.MakeGraph();
 A.PrintGraph(); cout << endl;
 //Раскраска с помощью рекурсивного обхода графа в глубину.
 //Инициализация.
 t = A.GetHead(); //Установлен рабочий указатель.
 while (t != A.GetTail())
 {
  t->Flag = TRUE; t->Color = 0;
  n++; t = (*t).Next;
 }
 // ------------------------------------ 
 //Построение вспомогательного множества MSet.
 A.Postr(n);
 cout << "Результат раскраски: ";
 A.Color(A.GetHead(), n);
 
 system("pause");
 return 0;
}

//Visual Studio 2015
// Последовательная раскраска графа при помощи
//обхода графа в ширину. 
//Граф представлен структурой Вирта.
#include <iostream>
#include <windows.h>
using namespace std;
 
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct Leader *Lref; // Тип: указатель на заголовочный узел.
typedef struct Trailer *Tref; // Тип: указатель на дуговой узел.
 
                              //Описание типа заголовочного узла.
typedef struct Leader
{
 int Key; //Имя заголовочного узла.
 int Count; //Количество предшественников.
 int Color; //Цвет раскраски.
 Boolean Flag; //Флаг посещения узла при обходе.
 Tref Trail; //Указатель на список смежности.
 Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
};
 
//Описание типа дугового узла.
typedef struct Trailer
{
 Lref Id;
 Tref Next;
};
 
//Описание типа узла очереди.
typedef Lref TipElement; //Указатель на звено заголовочного списка.
typedef struct Zveno *svqz;
typedef struct Zveno
{
 TipElement Element; //Указатель на список смежности.
 svqz Sled;
};
 
class Spisok
{
private:
 Lref Head; //Указатель на голову списка заголовочных узлов.
 Lref Tail; //Указатель на фиктивный элемент
            // в конце списка заголовочных узлов.
 int MSet[256]; //Вспомогательное множество, содер- 
                //жащее 0,1,2...,n.
 void Udalenie_A(svqz *, svqz *, TipElement *);
 void Dobavlenie(svqz *, svqz *, TipElement);
 void SearchGraph(int, Lref *);
public:
 Spisok() {//Инициализация списка заголовочных узлов.
  Head = Tail = new (Leader);
 }
 Lref GetHead() { return Head; }
 Lref GetTail() { return Tail; }
 void MakeGraph();
 void PrintGraph();
 void Color(Lref, int);
 void Postr(int);
};
 
void Spisok::Postr(int n)
//Построение вспомогательного множества MSet.
{
 for (int i = 0; i<256; i++)
  MSet[i] = (i <= n) ? 1 : 0;
}
 
void Spisok::SearchGraph(int w, Lref *h)
//Функция возвращает указатель на заголовочный узел
//с ключом w в графе, заданном структурой Вирта с указателем Head.
{
 *h = Head; (*Tail).Key = w;
 while ((**h).Key != w) *h = (**h).Next;
 if (*h == Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
 {
  Tail = new (Leader); (**h).Count = 0;
  (**h).Trail = NULL; (**h).Next = Tail;
 }
}
 
void Spisok::MakeGraph()
//Функция возвращает указатель Head на структуру
//Вирта, соответствующую ориентированному графу.
{
 int x, y;
 Lref p, q; //Рабочие указатели.
 Tref t, r; //Рабочие указатели.
 Boolean Res; //Флаг наличия дуги.
 cout << "Вводите начальную вершину дуги: ";
 cin >> x;
 while (x != 0)
 {
  cout << "Вводите конечную вершину дуги: "; cin >> y;
  //Определим, существует ли в графе дуга (x,y)?
  SearchGraph(x, &p); SearchGraph(y, &q);
  r = (*p).Trail; Res = FALSE;
  while ((r != NULL) && (!Res))
   if ((*r).Id == q) Res = TRUE;
   else r = (*r).Next;
   if (!Res) //Если дуга отсутствует, то поместим её в граф.
   {
    t = new (Trailer); (*t).Id = q;
    (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++;
   }
   cout << "Вводите начальную вершину дуги: "; cin >> x;
 }
}
 
void Spisok::PrintGraph()
//Вывод структуры Вирта, заданной указателем
//Head и соответствующей ориентированному графу.
{
 Lref p; //Рабочий указатель.
 Tref q; //Рабочий указатель.
 
 p = Head;
 while (p != Tail)
 {
  cout << (*p).Key << "("; q = (*p).Trail;
  while (q != NULL)
  {
   cout << (*(*q).Id).Key; q = (*q).Next;
  }
  cout << ")"; p = (*p).Next; cout << " ";
 }
}
 
void Spisok::Dobavlenie(svqz *L, svqz *R, TipElement elem)
//Добавление элемента elem в очередь, заданную указателями L и R.
{
 svqz K = new (Zveno);
 
 K->Element = elem; K->Sled = NULL;
 if (*L == NULL)
 {
  (*L) = K; (*R) = K;
 }
 else { (*R)->Sled = K; (*R) = K; }
}
 
void Spisok::Udalenie_A(svqz *L, svqz *R, TipElement *A)
//Удаление элемента из очереди, заданной указателями L и R и
//помещение удаленного элемента в переменную A.
{
 svqz q;
 
 if ((*L) != NULL)
  if ((*L)->Sled != NULL)
  {
   (*A) = (*L)->Element; q = (*L);
   (*L) = (*L)->Sled; delete q;
  }
  else {
   (*A) = (*L)->Element; delete *L;
   (*L) = (*R) = NULL;
  }
}
 
void Spisok::Color(Lref H, int n)
//Последовательная раскраска графа при помощи обхода графа
//в ширину, начиная с вершины, заданной указателем H
//(нерекурсивный обход).
{
 svqz L;   // Указатель на начало очереди.
 svqz R;   // Указатель на конец  очереди.
 Lref p;   // Рабочий указатель.
 Tref t;   // Рабочий указатель.
 Tref t1;
 int i;    // Параметр цикла.
 Boolean Fl;
 
 L = R = NULL; // Создание пустой очереди.
 Dobavlenie(&L, &R, H); H->Flag = FALSE;
 while (L != NULL)
 {  //Пока очередь не пуста...
  Udalenie_A(&L, &R, &p);
  t = p->Trail;
  //Сейчас мы находимся в вершине r->Key.
  //Исключим цвета всех вершин, смежных вершине 
  //r->Key, из множества MSet.
  t1 = t;
  while (t1 != NULL)
  {
   MSet[t1->Id->Color] = 0; t1 = t1->Next;
  }
  //Выбор цвета вершины - "первого" элемента множества MSet.
  Fl = TRUE; i = 1;
  while (Fl)
   if (MSet[i]) Fl = FALSE; else  i++;
  p->Color = i;   //Цвет присвоен!
  cout << "(" << p->Key << "," << p->Color << ") ";
  //Восстановление вспомогательного множества MSet.
  for (i = 0; i<256; MSet[i++] = 0);
  for (i = 0; i <= n; MSet[i++] = 1);
  while (t != NULL)
  {
   if (t->Id->Flag)
   {
    Dobavlenie(&L, &R, t->Id);
    t->Id->Flag = FALSE;
   }
   t = t->Next;
  }
 }
}
 
int main()
{
 
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 //Если нет русских букв при вводе, поставьте шрифт Lucida Console в свойствах окна консоли
 
 
 Spisok A;
 Lref t; //Рабочий указатель для перемещения 
         // по списку заголовочных звеньев.
 int n = 0; //Количество вершин в графе.
 
            //Построение графа и вывод его структуры Вирта.
 A.MakeGraph();
 A.PrintGraph(); cout << endl;
 //Раскраска с помощью рекурсивного обхода графа в ширину.
 //Инициализация.
 t = A.GetHead(); //Установлен рабочий указатель.
 while (t != A.GetTail())
 {
  t->Flag = TRUE; t->Color = 0;
  n++; t = (*t).Next;
 }
 // ------------------------------------ 
 //Построение вспомогательного множества MSet.
 A.Postr(n);
 cout << "Результат раскраски: ";
 A.Color(A.GetHead(), n);
 system("pause");
 return 0;
}

//Visual Studio 2015
//Последовательная раскраска графа, представленного с помощью
//модифицированных списков смежности.
#include <iostream>
#include <windows.h>
using namespace std;
 
 
#define TRUE 1
#define FALSE 0
#define XRY 8  //Количество вершин графа.
typedef int Boolean;
typedef struct zveno *svqz;
typedef struct zveno
{
 int Key;  // Вершина графа.
 svqz Up;  // Указатель на смежную вершину.
 svqz Sled;// Указатель на следующую смежную вершину.
};
 
class Spisok
{
private:
 svqz Beg[XRY + 1]; //Массив указателей на вершины.
 void Add_Ver(int);
 int Find(int, int, svqz *);
 void Add_duga(int, int);
 void Make(int, int);
 void Delinenok(int, int);
 void Del_Duga(int, int);
 void Del_Ver(int);
 int Find_Color(int, int, svqz *);
public:
 Spisok();
 void Init_Graph();
 void Make_Graph();
 void Print_Graph();
 void Color();
 void Print_Color();
};
 
Spisok::Spisok()
{
 for (int i = 0; i <= XRY; Beg[i++] = NULL);
}
 
void Spisok::Add_Ver(int x)
//Функция создания вершины x.
{
 svqz Ukaz = new (zveno);
 
 Ukaz->Sled = NULL;
 Beg[x] = Ukaz;
}
 
void Spisok::Init_Graph()
//Функция инициализации модифицированных списков смежности.
{
 for (int i = 1; i <= XRY; i++) Add_Ver(i);
}
 
int Spisok::Find(int x, int y, svqz *UkZv)
//Функция проверки смежности вершин y и x. Функция возвращает
//TRUE, если  вершина x смежна с вершиной y. Указатель *UkZv,
//возвращает указатель на место y в списке  смежности x. Если
//вершина x не смежна с вершиной y, то UkZv есть NULL.
{
 svqz Ukaz;
 
 Ukaz = Beg[x]->Sled;
 while (Ukaz != NULL && Ukaz->Key != y)
  Ukaz = Ukaz->Sled;
 *UkZv = Ukaz;
 return  (Ukaz != NULL);
}
 
void Spisok::Add_duga(int x, int y)
//Функция создания дуги (x,y).
{
 svqz Ukaz = new (zveno);
 
 Ukaz->Sled = Beg[x]->Sled; Ukaz->Key = y;
 Beg[x]->Sled = Ukaz;
}
 
void Spisok::Make(int x, int y)
//Функция создания ребра {x,y}.
{
 svqz Ukaz;
 
 if (!Find(x, y, &Ukaz))
 {
  Add_duga(x, y);
  if (x != y) Add_duga(y, x);
  Beg[x]->Sled->Up = Beg[y];
  Beg[y]->Sled->Up = Beg[x];
 }
}
 
void Spisok::Make_Graph()
//Функция построения модифицированных списков смежности.
{
 int f;
 
 for (int i = 1; i <= XRY; i++)
 {
  cout << "Введите вершины, смежные с " << i << "-й вершиной: ";
  cin >> f;
  while (f != 0)
  {
   Make(i, f);
   cout << " ";
   cin >> f;
  }
  cout << endl;
 }
}
 
void Spisok::Delinenok(int x, int y)
//Функция удаления дуги (x,y).
{
 svqz Ukaz;
 svqz Ukazlenok;
 
 Ukazlenok = Beg[x]; Ukaz = Beg[x]->Sled;
 while (Ukaz != NULL && Ukaz->Key != y)
 {
  Ukazlenok = Ukaz; Ukaz = Ukaz->Sled;
 }
 if (Ukaz != NULL)
 {
  Ukazlenok->Sled = Ukaz->Sled;
  delete Ukaz;
 }
}
 
void Spisok::Del_Duga(int x, int y)
//Функция удаления ребра {x,y}.
{
 Delinenok(x, y); Delinenok(y, x);
}
 
void Spisok::Del_Ver(int x)
//Функция удаления вершины x.
{
 svqz Ukaz;
 svqz Ukazlenok;
 
 for (int i = 1; i <= XRY; i++) Delinenok(i, x);
 Ukaz = Beg[x]; Beg[x] = NULL;
 while (Ukaz != NULL)
 {
  Ukazlenok = Ukaz->Sled;
  delete Ukaz; Ukaz = Ukazlenok;
 }
}
 
void Spisok::Print_Graph()
//Функция вывода содеpжимого модифицированных
//списков смежности.
{
 svqz UkZv;
 
 for (int i = 1; i <= XRY; i++)
 {
  if (Beg[i] != NULL)
  {
   UkZv = Beg[i]->Sled;
   cout << i << " - ";
   while (UkZv != NULL)
   {
    cout << " " << UkZv->Key;
    UkZv = UkZv->Sled;
   }
  }
  cout << endl;
 }
}
 
int Spisok::Find_Color(int x, int c, svqz *UkZv)
//Функция  выявления возможности раскраски вершины  x цветом c. 
//Функция  возвращает TRUE, если вершину  x  можно  раскрасить. 
//Указатель *UkZv, возвращает указатель на вершину, смежную с x 
//и раскрашенную цветом c. Если вершину x можно раскрасить, то 
//*UkZv есть NULL.
{
 int i = 1;
 
 while (!(Find(x, i, &(*UkZv)) &&
  Beg[i]->Key == c) &&
  i != x) i++;
 return (i == x);
}
 
void Spisok::Color()
//Функция последовательной раскраски графа, заданного
//модифицированными списками смежности Beg.
{
 int i = 1;
 int c = 1;
 svqz UkZv;
 
 while (Beg[i] == NULL && i <= XRY) i++;
 if (i != XRY)
 {
  Beg[i]->Key = c;
  i++;
  while (i <= XRY)
   if (Beg[i] != NULL)
   {
    c = 1;
    while (!Find_Color(i, c, &UkZv)) c++;
    Beg[i]->Key = c; i++;
   }
   else  i++;
 }
 else  cout << "Граф отсутствует!";
}
 
void Spisok::Print_Color()
//Функция вывода раскраски графа, заданного
//модифицированными списками смежности Beg.
{
 for (int i = 1; i <= XRY; i++)
  if (Beg[i] != NULL)
   cout << " Color " << i << " - " << Beg[i]->Key << endl;
}
 
 
int main()
{
 
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 //Если нет русских букв при вводе, поставьте шрифт Lucida Console в свойствах окна консоли
 
 Spisok A;
 
 //Инициализация графа.
 A.Init_Graph();
 //Построение графа.
 A.Make_Graph();
 //Вывод графа.
 A.Print_Graph();
 
 
 //Последовательная раскраска графа, представленного
 //модифицированными списками смежности.
 A.Color();
 A.Print_Color();
 system("pause");
 return 0;
}