gpt4 book ai didi

java - 美国 map 的四色定理Java实现

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:20:34 43 4
gpt4 key购买 nike

我正在尝试为每个状态分配一种颜色,以便没有两个相邻状态共享相同的颜色 ( 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 <String> statestemp = new ArrayList <String> ();
ArrayList <State> states = new ArrayList <State> ();

// 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 <String> adj = new ArrayList <String> ();

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 <String> getAdj() {
return this.adj;
}
}

我想开始分配颜色,但我不确定如何进行比较。

如有任何建议,我们将不胜感激!

最佳答案

四色映射算法非常复杂,您必须在代码中处理 1476 种特殊情况。如果能多留一种颜色,五色映射算法就可以满足你的要求,简单多了,还有一个nice writeup on it at devx.com

对于美国 map 的特殊情况,有许多州的邻居少于五个(例如佛罗里达州),因此您只需解决算法的第一种情况,即:

  1. 将 map 转换为图表(看起来您已经这样做了或者与您的邻接表很接近)
  2. 在图中选择一个邻居少于五个的节点(州)并将其从图中删除。这将降低图表的复杂性,并可能导致一些以前有五个或更多邻居的节点现在少于五个。
  3. 从更新的图中选择另一个少于五个邻居的节点并将其删除。
  4. 继续,直到您从图中删除了所有节点。
  5. 以与删除节点相反的顺序将节点添加回图中(考虑此处的堆栈)。
  6. 使用当前邻居未使用的颜色为添加的节点着色。
  7. 继续,直到您为整个图表着色。

关于java - 美国 map 的四色定理Java实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20306116/

43 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com