Каким алгоритмом раскрашивается граф?

Question

[Dobbi]

Помогите определить название алгоритма раскраски

// Раскрасить
void Graph::colorize()
{
// Находим степени вершин
// Степень вершины - количество принадлежащих ей ребер
std::vector degree;// Вектор со степенями

// Добавим в вектор номера вершин
for (int x = 0; x < this->tops.size(); x++)
degree.push_back(0);

// Проставим степени
for (int x = 0; x < this->edges.size(); x++)
{
++degree.at(this->edges.at(x).top1);
++degree.at(this->edges.at(x).top2);
}

// Упорядочим
std::sort (degree.begin(), degree.end ());

// Вектор с векторами смежных вершине вершин
std::vector > adjacentTops;
// Несмежных
// std::vector > unAdjacentTops;

// Найдем смежные вершины
for (int x = 0; x < this->tops.size(); x++)
{
// Вектор со смежными текущей вершине вершинами (сама вершина тоже окажется смежной самой себе, но это не важно)
std::vector currentAdjacentTops;

// Проходим по ребрам
for (int e = 0; e < this->edges.size(); e++)
{
if (this->edges.at(e).top1 == x)
currentAdjacentTops.push_back(this->edges.at(e).top2);

if (this->edges.at(e).top2 == x)
currentAdjacentTops.push_back(this->edges.at(e).top1);
}

adjacentTops.push_back(currentAdjacentTops);
}

// // Найдем несмежные вершины
// for (int x = 0; x < this->tops.size(); x++)
// {
// std::vector curV;
// for (int i = 0; i < this->tops.size(); i++)
// {
// curV.push_back(0);
// }
// unAdjacentTops.push_back(curV);
// }

// for (int x = 0; x < this->tops.size(); x++)
// {
// for (int i = 0; i < adjacentTops.at(x).size (); i++)
// {
// std::vector curV = adjacentTops.at(x);
// unAdjacentTops.at(x).at(curV.at (i)) = -1;
// }
// }

int countColorize = 0;// Число раскрашенных вершин
int countColors = 0;

// Заметка: после сортировки обходить вектор декрементом
for (int x = degree.size() - 1; x >= 0; x--)
{
// if (countColorize >= this->tops.size())
// break;

++countColors;

// Текущий рандомный цвет
QColor currentColor = QColor (rand () % 255, rand () % 255, rand () % 255, 255);

this->tops.at(x).color = currentColor;

// Обходим вершины - красим все в этот цвет все вершины, у которых нет соседей с данным цветом
for (int i = 0; i < this->tops.size(); i++)
{
bool mayColorize = true;

// Обходим соседей вершины, и если никакой сосед не окрашен в данный цвет, красим вершину
for (int s = 0; s < adjacentTops.at(i).size (); s++)
{
if (this->tops.at(adjacentTops.at(i).at(s)).color == currentColor)
{
mayColorize = false;
}
}

if (mayColorize)
{
this->tops.at(i).color = currentColor;
++countColorize;
}
}
}

this->chromaticNumber = countColors;

}

Answer 1

[bobrovskyserg]

Это жадный алгоритм раскраски.
При удачном раскладе даёт оптимальную по числу цветов раскраску, но обычно - нет.
Точное решение достигается, увы, полным перебором.