四色定理的Java实现的美国地图 [英] Four color theorem Java implementation of U.S. map

问题描述

我在尝试一种颜色分配给每个状态，以便没有两个相邻的国家共享相同的颜色（的 http://en.wikipedia.org/wiki/Four_color_theorem ）。该计划将输出的每个国家和它的颜色。

I am attempting to assign a color to each of the states so that no two adjacent states share the same color (http://en.wikipedia.org/wiki/Four_color_theorem). The program will output each state and its color.

我读的文本文件与48个州的格式如下（2未连接）：

I'm reading in a text file with the following format for 48 states (2 aren't connected):

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
...

例：

阿拉巴马倒是佛罗里达州，密西西比州，田纳西州和格鲁吉亚。

Alabama touches Florida, Mississippi, Tennessee, and Georgia.

阿肯色倒是路易斯安那州，得克萨斯州，等等。

Arkansas touches Louisiana, Texas, etc.

这是我的code到目前为止：

This is my code so far:

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;
    }
}

我在的地步，我想首先指定颜色，但我不能确定如何去进行比较。

I am at the point where I would like to begin assigning colors, but I am unsure how to go about making comparisons.

任何建议将是AP preciated！

Any suggestions would be appreciated!

推荐答案

四色映射算法很复杂，有1476，你必须处理您的code特殊情况。如果你能腾出多了一个颜色，五种颜色映射算法将满足您的要求，就是要简单得多，并且有一个的在devx.com 不错的书面记录就可以了。

The four-color mapping algorithm is very complex, with 1476 special cases that you have to handle in your code. If you can spare one more color, the five color mapping algorithm will meet your requirements, is much simpler, and there is a nice writeup on it at devx.com

有关的美国地图的特殊情况下，也有很多国家有不到五邻国（例如，佛罗里达州），所以你只需要处理算法，它是这的第一种情况：

For the special case of a United States map, there are many states with less than five neighbors (e.g, Florida), so you only have to address the first case of the algorithm, which is this:

1. 地图转换为图形（看起来像你这样做或接近你的邻接表）
2. 选择在图中的一个节点（州）配不到五年的邻居，从图中删除。这将降低你的图形的复杂性，并可能会导致一些节点previously有五个或更多的邻居到现在有少于五个。
3. 选择从更新的图，不到五年的邻居另一个节点，并删除它。
4. 继续，直到你从图中删除了所有的节点。
5. 添加节点备份的曲线从中删除它们相反的顺序（想想堆在这里）。
6. 颜色与不使用任何目前的邻国颜色增加的节点。
7. 继续，直到你着色整个图形。

这篇关于四色定理的Java实现的美国地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！