我需要一种算法来获取图的色数

Question

给定图的邻接矩阵，我需要获取色数（绘制图的每个节点所需的最小颜色数，以便相邻节点获得不同的颜色）。

最好应该是java算法，我不关心性能。

谢谢。

编辑：最近引入了一个修复程序，因此答案更准确。现在它将重新检查他的位置与他之前的位置。

现在出现了一个新问题。哪个会更好地提高他的“数字颜色”？我所在的节点，还是我正在访问的节点（询问我是否与其相邻）？

public class Modelacion {

    public static void main(String args[]) throws IOException{

    //  given the matrix ... which i have hidden the initialization here

        int[][] matriz = new int[40][40];

        int color[] = new int[40];

        for (int i = 0 ; i<40;i++)
            color[i]=1;

        Cromatico c = new Cromatico(matriz, color);

    }
}

import java.io.IOException;


public class Cromatico {

Cromatico(int[][]matriz, int[] color, int fila) throws IOException{

        for (int i = 0; i<fila;i++){
            for (int j = 0 ; j<fila;j++){
                if (matriz[i][j] == 1 && color[i] == color [j]){
                    if (j<i)
                        color [i] ++;
                    else
                        color [j] ++;
                }
            }
        }

        int numeroCromatico = 1;
        for (int k = 0; k<fila;k++){
            System.out.print(".");
            numeroCromatico = Math.max(numeroCromatico, color[k]);  
        }

        System.out.println();
        System.out.println("el numero cromatico del grafo es: " + numeroCromatico);

    }
}

Answer 1

超级慢，但它应该可以工作：

int chromaticNumber(Graph g) {
  for (int ncolors = 1; true; ncolors++) {
    if (canColor(g, ncolors)) return ncolors;
  }
}

boolean canColor(Graph g, int ncolors) {
  return canColorRemaining(g, ncolors, 0));
}

// recursive routine - the first colors_so_far nodes have been colored,
// check if there is a coloring for the rest.
boolean canColorRemaining(Graph g, int ncolors, int colors_so_far) {
  if (colors_so_far == g.nodes()) return true;
  for (int c = 0; c < ncolors; c++) {
    boolean ok = true;
    for (int v : g.adjacent(colors_so_far)) {
      if (v < colors_so_far && g.getColor(v) == c) ok = false;
    }
    if (ok) {
      g.setColor(colors_so_far, c);
      if (canColorRemaining(g, ncolors, colors_so_far + 1)) return true;
    }
  }
  return false;
}