Java 实现：3 种颜色给 4 顶点图着色，连边顶点颜色不同！

以下是用 Java 实现的给 4 顶点图着色的代码示例： ```java import java.util.Arrays; public class GraphColoring { // 检查当前颜色分配是否有效 public static boolean isSafe(int[][] graph, int[] color, int vertex, int c) { for (int i = 0; i < graph.length; i++) { if (graph[vertex][i] == 1 && color[i] == c) { return false; } } return true; } // 进行图着色的递归函数 public static boolean graphColoringUtil(int[][] graph, int m, int[] color, int vertex) { if (vertex == graph.length) { return true; } for (int c = 1; c <= m; c++) { if (isSafe(graph, color, vertex, c)) { color[vertex] = c; if (graphColoringUtil(graph, m, color, vertex + 1)) { return true; } color[vertex] = 0; } } return false; } // 主函数 public static boolean graphColoring(int[][] graph, int m) { int[] color = new int[graph.length]; Arrays.fill(color, 0); if (!graphColoringUtil(graph, m, color, 0)) { System.out.println("无法完成着色"); return false; } // 打印着色结果 for (int i = 0; i < graph.length; i++) { System.out.println("顶点 " + i + " 的颜色: " + color[i]); } return true; } public static void main(String[] args) { int[][] graph = {{0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}}; int m = 3; // 颜色数量 graphColoring(graph, m); } } ``` 额外需要注意的逻辑点： 1. 对于颜色分配的有效性判断要准确，确保连边顶点颜色不同。 2. 递归过程中回溯的处理要恰当，以便尝试所有可能的着色组合。 3. 处理好无法完成着色的情况，给出明确的提示信息。 ######[AI写代码神器 | 572点数解答 | 2024-11-28 09:30:28]