2

考虑是否可以使用 BFS 实现图形着色，我想出了下面的伪代码方法。

虽然它看起来像一个贪心算法，但我不确定它的正确性。有专家意见吗？

colors[MAX_COLORS];
colorsUsedSoFar[] = NIL;
like BFS, color first node u with colors[0] i.e color[u] = colors[0];
colorsUsedSoFar[] += colors[0];

for each node v adjacent to u{
  (if v not already colored){
     color[v] = color from the colorsUsedSoFar[] but NotUsedByItsAdjacents
     If all the colors in colorsUsedSoFar[] are used by adjacents, assign a new color to v)
  }
}

“像 BFS”，我的意思是使用队列并处理直到队列耗尽。

4

2 回答 2

1

如果您希望您的算法按 BFS 顺序为图形着色，那么我认为您的算法在正确的情况下是完全可以的，除非您在 for 循环内着色后没有将节点添加到队列中。这也是一种贪婪的方法。您正在贪婪地选择一个节点来根据级别首先着色。不是直截了当的贪婪，但我说有点。

于 2013-05-25T12:01:00.220 回答
1

这是一个贪心着色算法的例子。

广度优先搜索 (BFS) 将为您隐式选择排序。

所以算法是正确的，但并不总是给出最佳的颜色（即使用的颜色最少）。

更常见的排序是按顶点的度数对顶点进行排序，称为Welsh-Powell 算法。

于 2013-05-24T17:10:46.217 回答