这是我写的一个算法,用于查找图的色数 . 我无法弄清楚这个算法的时间复杂度 . 由于我有3个嵌套循环,我认为时间复杂度至少为n³ . 因为我也在迭代每个顶点的边缘,它会是O(n2ⁿ)周围的东西吗?这个算法也是正确的吗?
int ChromaticNumber()
{
for (int i = 0; i < Vertices.size(); ++i)
{
++Vertices[i].Color;
bool Ok = false;
while (!Ok)
{
Ok = true;
for (int j = 0; j < Vertices[i].Edges.size(); ++j)
{
int AdjacentVertex = Vertices[i].Edges[j];
if (Vertices[i].Color == Vertices[AdjacentVertex].Color)
{
++Vertices[i].Color;
Ok = false;
}
}
}
}
int MaxColor = 0;
for (int i = 0; i < Vertices.size(); ++i)
{
if (Vertices[i].Color > MaxColor)
MaxColor = Vertices[i].Color;
}
return MaxColor;
}