我试图为每个状态指定一种颜色,以便没有两个相邻的状态共享相同的颜色(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 { ArrayListstatestemp = 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 ArrayListadj = 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上有一个很好的写作
对于美国地图的特殊情况,有许多州的邻居少于五个(例如,佛罗里达州),因此您只需要解决算法的第一种情况,即:
将地图转换为图形(看起来您已完成此操作或与您的邻接列表关闭)
在图表上选择少于五个邻居的一个节点(状态),并将其从图表中删除.这将降低图形的复杂性,并可能导致以前有五个或更多邻居的某些节点现在少于五个.
从更新的图表中选择少于五个邻居的另一个节点并将其删除.
继续,直到您从图表中删除所有节点.
以与删除它们相反的顺序将节点添加回图形(在此处思考堆栈).
使用当前任何邻居未使用的颜色为添加的节点着色.
继续,直到您在整个图表中着色.