我正在阅读顶点着色算法。我看到文档解释了如何使用 BFS 解决问题(暗示问题可以在 O(|V|+|E|) 中解决)。但我也看到它提到这是一个 NP-hard 问题。
这两者如何结合？你能给点灯吗？
这是我遇到的算法，对我来说它看起来像是一般情况下的多项式解:
用数字标识每种颜色。从一个节点开始，并为其分配编号最少的颜色。使用 BFS 访问它的每个邻居。在访问一个节点时，检查它的每个邻居的颜色，并分配没有分配给任何邻居的颜色最少的颜色。
据说 BFS 方法仅适用于 2 种颜色。我明白为什么上述技术不能用于超过 2 种颜色
最佳答案
通常，当我想到面包优先搜索 (BFS) 时，我认为它适用于树，但顶点着色是一个图问题，而不是树问题。我想您可以通过采用以下规则将 BFS 应用于图形，即在移动到不同节点之前标记与当前节点相邻的所有节点。
首先，看一个基本示例，说明使用最低编号排序(称为顺序排序)的简单标记如何不起作用:
如果我们按顺时针顺序(A 到 J)标记节点，我们最终得到 4 色，而实际上该图具有 2 色。现在，您的规则，优先标记相邻节点将起作用，因为它是双色的。但是，您的规则不适用于 3 种着色，例如:
在这个例子中我们选择A作为“树”的根，首先做它的 child B和C。然后，我们选择 child B，因为它的字母顺序低于 C，并且是 B 的所有子级。我们最终得到一个 4 色图，而实际上该图可以是 3 色图。
关于algorithm - 为什么顶点着色是 NP-hard？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21798823/