图的着色问题-回溯解决java

图的着色问题是指给定一个无向图，要求为每个节点着上一种颜色，使得相邻节点之间的颜色不同。这个问题可以用回溯算法来解决。

回溯算法的基本思路是递归地枚举所有可能的解，并在搜索过程中不断地剪枝，避免无效搜索。对于图的着色问题，我们可以从图的任意一个节点开始，尝试给它着上一种颜色，然后递归地对与它相邻的节点进行着色。如果当前节点已经被着色，就跳过它；如果当前节点无法着色，就返回上一级递归，尝试其他的颜色。如果所有节点都已经被着色，就找到了一个可行解。

下面是一个简单的 Java 代码实现：

public class GraphColoring {
    private int[][] graph;  // 无向图
    private int[] colors;   // 节点颜色
    private int n;          // 节点数
    private int m;          // 颜色数

    public GraphColoring(int[][] graph, int m) {
        this.graph = graph;
        this.n = graph.length;
        this.colors = new int[n];
        this.m = m;
    }

    public void solve() {
        if (dfs(0)) {
            printSolution();
        } else {
            System.out.println("No solution");
        }
    }

    private boolean dfs(int node) {
        if (node == n) {
            return true;  // 所有节点都已经着色，找到一个可行解
        }
        for (int i = 1; i <= m; i++) {  // 枚举所有可能的颜色
            if (isValidColor(node, i)) {
                colors[node] = i;  // 给节点着色
                if (dfs(node + 1)) {
                    return true;  // 成功找到一个可行解，直接返回
                }
                colors[node] = 0;  // 回溯，恢复节点颜色
            }
        }
        return false;  // 没有找到可行解
    }

    private boolean isValidColor(int node, int color) {
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && colors[i] == color) {
                return false;  // 与相邻节点颜色相同，不符合要求
            }
        }
        return true;
    }

    private void printSolution() {
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + " is colored " + colors[i]);
        }
    }
}

在这个代码中，我们首先定义了一个 `GraphColoring` 类来表示图的着色问题。它包含一个私有的二维数组 `graph` 来表示无向图，一个整型数组 `colors` 来存储每个节点的颜色，一个整数 `n` 来表示节点数，和一个整数 `m` 来表示颜色数。

在 `solve` 方法中，我们调用 `dfs` 方法来搜索所有可能的解。如果找到一个可行解，就输出它；否则输出 "No solution"。

在 `dfs` 方法中，我们先判断当前节点是否已经被着色，如果是，则跳过它；否则枚举所有可能的颜色，并检查颜色是否合法。如果颜色合法，就给节点着色，并递归地对相邻节点进行着色。如果找到一个可行解，就直接返回；否则回溯，恢复节点颜色。

在 `isValidColor` 方法中，我们检查给定颜色是否与相邻节点的颜色相同。如果相同，就表示该颜色不符合要求。

最后，在 `printSolution` 方法中，我们输出每个节点的颜色。