四色定理Java实现美图
我试图为每个状态指定一种颜色，以便没有两个相邻的状态共享相同的颜色（ http://en.wikipedia.org/wiki/Four_color_theorem ）。 程序将输出每个状态及其颜色。
我正在读取一个文本文件，其格式为48个状态（2个未连接）：
al,fl,ms,tn,ga ar,la,tx,ok,mo,tn,ms az,ca,nv,ut,nm ca,az,nv,or co,wy,ut,nm,ok,ks,ne ... 例：
阿拉巴马州接触佛罗里达州，密西西比州，田纳西州和佐治亚州。
阿肯色州接触路易斯安那州，德克萨斯州等。
到目前为止这是我的代码：
MapColor.java import java.io.*; import java.util.*; public class MapColor { public static void main(String[] args) throws IOException { ArrayList statestemp = new ArrayList (); ArrayList states = new ArrayList (); // read in each line BufferedReader reader = new BufferedReader(new FileReader("usa.txt")); String line = null; while ((line = reader.readLine()) != null) { statestemp.add(line); } reader.close(); // create all state objects and adjacencies for (int i = 0; i < statestemp.size(); i++) { State st = new State(); String[] str = statestemp.get(i).split(","); st.setName(str[0]); for (int j = 1; j < str.length; j++) { st.addAdj(str[j]); } states.add(st); } // set colors // print out states and adjacencies for (State s : states) { System.out.println("Name: " + s.getName()); System.out.println("Color: " + s.getColor()); System.out.print("Adj: "); s.getAdj(); System.out.println(); System.out.println(); } } }
和
State.java import java.util.ArrayList; public class State { public String n = null; public int c = 0; public ArrayList adj = new ArrayList (); public String getName() { return n; } public void setName(String name) { this.n = name; } public int getColor() { return c; } public void setColor(int color) { this.c = color; } public void addAdj(String s) { this.adj.add(s); } public ArrayList getAdj() { return this.adj; } }
我正处于开始分配颜色的地步，但我不确定如何进行比较。
任何建议，将不胜感激！
四色映射算法非常复杂，您需要在代码中处理1476个特殊情况。 如果你可以再多一个颜色，五色映射算法将满足你的要求，更简单，并在devx.com上有一个很好的写作
对于美国地图的特殊情况，有许多州的邻居少于五个（例如佛罗里达州），因此您只需要解决算法的第一种情况，即：
- 将地图转换为图形（看起来您已经完成此操作或与您的邻接列表关闭）
- 在图表上选择少于五个邻居的一个节点（状态），并将其从图表中删除。 这将降低图表的复杂性，并可能导致之前有五个或更多邻居的某些节点现在少于五个。
- 从更新的图表中选择少于五个邻居的另一个节点并将其删除。
- 继续，直到您从图表中删除所有节点。
- 以与删除它们相反的顺序将节点添加回图形（在此处思考堆栈）。
- 使用当前任何邻居未使用的颜色为添加的节点着色。
- 继续，直到您在整个图表中着色。
我会建立可用颜色的队列，并在每个状态中迭代分配（即出列/排队）颜色。 这是贪婪着色背后的基本思想： http ： //en.wikipedia.org/wiki/Greedy_coloring 。 这可能不是最优的，但你只有48个顶点（是的，我认为这是一个图形）。
在这个例子中你可以做的是创建State类，以便它自己知道它周围有多少个状态，以及它们的颜色是什么。 这样，您可以创建一个方法来检查任何相邻状态是否具有相同的颜色（或者该状态是否具有有效颜色）。 这样你就可以循环遍历状态并检查每个状态的颜色是否有效。
另外，这将允许您通过询问所有相邻状态的颜色来实现一种评估状态应该是哪种颜色的方法，然后只需指定该状态，无论返回什么颜色。 你可以从美国的一个角落开始，然后以这种方式向下工作。
希望能帮助您解决问题！