我正在使用 Java 进行图形着色项目。我需要使用四色定理实现四种不同的图形着色算法。我对名为少数邻居贪婪算法的算法之一有疑问。
我有一张地图，其中包含一堆多边形对象（存储在数组列表中）。另外，我有一个 2D 布尔数组，它表示不同多边形的邻接关系。
我从理论上知道该算法：我有一个优先级队列来存储我的未着色多边形。基于邻接计数的队列顺序。如果一个多边形的邻居很少，它被认为比一个有很多邻居的多边形好。无论如何，该算法应该重复从优先队列中绘制一个多边形，并尝试根据它的邻接对其进行着色。
不幸的是，我在实施部分遇到了问题。我根据邻接计数获得了优先队列，但是在为这些多边形分配颜色时遇到了问题。如果有人研究过这种算法，或者有想法的人，请与我分享。我需要一些想法来加快实施部分。
提前致谢。
您应该准确说明实施部分需要什么样的帮助。“我在分配颜色时遇到问题”怎么办？
包含存储在数组列表中的多边形对象的地图是输入？我假设你的多边形是图中的节点。
您可能应该构建一个 Graph 数据结构并对其进行导航。经典的 C 风格方法是使用数组作为节点和边，并使其看起来很复杂。
由于使用组合的 OOP自然生成对象图，这是在这里使用的好方法。
图本质上由 2 个元素组成：节点和边。
从 Node 类开始。它有一个颜色、一个 id 和一个边的 ArrayList。边形成两个节点之间的关系，并且可能具有权重和方向。
从输入中创建节点和边（请记住，如果新节点不存在，则创建它）。然后通过选择一个未标记的节点来运行最近邻算法（静态方法可能适用于此，或者您可以真正在现实生活中练习并实施策略模式）。
不过要注意周期！
您听起来像是在尝试首先为最低度数的节点着色。这似乎是倒退的，您应该首先为最高程度的节点着色。例如，如果您有 4 种颜色可供选择，则 3 级节点将始终是可着色的。
您确实意识到任何贪心算法都可能无法找到 4 色，即使图形是 4 色的。
查看Wikipedia 页面以获取一些有用的指示。