我正在使用 Java 进行图形着色项目。我需要使用四色定理实现四种不同的图形着色算法。我对名为少数邻居贪婪算法的算法之一有疑问。
我有一张地图,其中包含一堆多边形对象(存储在数组列表中)。另外,我有一个 2D 布尔数组,它表示不同多边形的邻接关系。
我从理论上知道该算法:我有一个优先级队列来存储我的未着色多边形。基于邻接计数的队列顺序。如果一个多边形的邻居很少,它被认为比一个有很多邻居的多边形好。无论如何,该算法应该重复从优先队列中绘制一个多边形,并尝试根据它的邻接对其进行着色。
不幸的是,我在实施部分遇到了问题。我根据邻接计数获得了优先队列,但是在为这些多边形分配颜色时遇到了问题。如果有人研究过这种算法,或者有想法的人,请与我分享。我需要一些想法来加快实施部分。
提前致谢。