java - 图着色算法(贪心着色)

Question

我正在使用 Java 进行图形着色项目。我需要使用四色定理实现四种不同的图形着色算法。我对名为少数邻居贪婪算法 的算法之一有疑问。

我有一张 map ，其中包含一堆多边形对象(存储在数组列表中)。另外，我有一个二维 boolean 数组，表示不同多边形的邻接关系。

我从理论上知道该算法:我有一个优先级队列来存储我的未着色多边形。基于邻接计数的队列顺序。如果多边形的邻居很少，则认为它比邻居多的多边形更好。不管怎样，该算法应该从优先队列中重复绘制一个多边形，并尝试根据它的邻接点给它着色。

不幸的是，我在实现部分遇到了问题。我得到了基于邻接计数的优先级队列，但是我在为这些多边形分配颜色时遇到了问题。如果有人研究过这种算法，或者有任何想法，请与我分享。我需要一些想法来加快实现部分。

提前致谢。

Answer 1

您应该准确说明您在实现部分需要什么样的帮助。 “我在分配颜色时遇到问题”怎么办？

包含存储在数组列表中的多边形对象的 map 以及用于邻接的单独二维 boolean 数组是输入吗？我假设你的多边形是图中的节点。

您可能应该构建一个图形数据结构并在其中导航。经典的 C 风格方法是对节点和边使用数组，making it look complex .

自 OOP using Composition自然生成一个 graph of objects这是在这里使用的好方法。

图基本上由 2 个元素组成:节点和边。

从 Node 类开始。它有一个颜色、一个 id 和一个边的 ArrayList。边在 2 个节点之间形成关系，并且可能具有权重和方向。

根据输入创建节点和边(请记住，如果不存在新节点，则创建它)。然后运行 ​​nearest neighbor algorithm通过选择一个未标记的节点(静态方法可能对此很有效，或者您可以真正在现实生活中练习并实现策略模式)。

不过要注意周期!