threecolor.java

采用回溯法

public class ThreeColor {

	// 设置不相邻的顶点间距离
	int infinite = Integer.MAX_VALUE;
	// 标识是否找到结果
	boolean flag = false;
	// 图中顶点数
	int max = 5;
	//当前顶点数
	int n;
	// 顶点所上的颜色
	int[] c;
	// 图的邻接矩阵
	int[][] graph = { { 0, 1, 1, infinite, infinite },
			{ 1, 0, infinite, 1, 1 }, { 1, infinite, 0, 1, 1 },
			{ infinite, 1, 1, 0, 1 }, { infinite, 1, 1, 1, 0 } };

	public ThreeColor() {
		c = new int[max];
	}

	public void graphcolor() {
		n = 0;
		while (n >= 0) {
			while (c[n] <= 2) {
				c[n]++;
				if (!isRightColor())
					continue;
				if (n == max - 1) {
					for (int i = 0; i < max; i++) {
						System.out.print(c[i] + " ");
					}
					System.out.println();
				} else
					n++;
			}
			c[n] = 0;
			n--;
		}
	}

	// 
	boolean isRightColor() {
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++) {
				if (i != j && graph[i][j] == 1 && c[i] == c[j])
					return false;
			}
		return true;
	}

	public static void main(String[] args) {
		ThreeColor tc = new ThreeColor();
		tc.graphcolor();
	}

}