图的着色问题

问题描述：给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

回溯算法

/**
 * 图的着色问题 - 回溯算法实现
 */
class GraphColoring {
    /**
     * @param {number[][]} graph - 图的邻接矩阵表示
     * @param {number} m - 可用的颜色数量
     */
    constructor(graph, m) {
      this.graph = graph;
      this.numVertices = graph.length;
      this.m = m; // 可用颜色的数量
      this.colors = new Array(this.numVertices).fill(0); // 存储每个顶点的颜色，0表示未着色
    }
  
    /**
     * 检查为顶点 v 分配颜色 c 是否安全（合法）
     * @param {number} v - 当前顶点的索引
     * @param {number} c - 尝试分配的颜色 (1 to m)
     * @returns {boolean} - 是否可以分配
     */
    isSafe(v, c) {
      for (let i = 0; i < this.numVertices; i++) {
        // 检查 v 和 i 是否是邻居，以及邻居 i 是否已经使用了颜色 c
        if (this.graph[v][i] === 1 && this.colors[i] === c) {
          return false;
        }
      }
      return true;
    }
  
    /**
     * 递归的工具函数，用于解决着色问题
     * @param {number} v - 当前正在处理的顶点索引
     * @returns {boolean} - 是否找到了一个解
     */
    solveColoringUtil(v) {
      // --- Base Case: 基本情况 ---
      // 如果所有顶点都已经被成功着色，说明找到了一个解
      if (v === this.numVertices) {
        return true;
      }
  
      // --- Recursive Step: 递归步骤 ---
      // 尝试为顶点 v 分配每一种颜色
      for (let c = 1; c <= this.m; c++) {
        // 检查为顶点 v 分配颜色 c 是否安全
        if (this.isSafe(v, c)) {
          // 分配颜色
          this.colors[v] = c;
  
          // 递归地为下一个顶点着色
          if (this.solveColoringUtil(v + 1)) {
            return true; // 如果后续的顶点都成功着色，返回 true
          }
  
          // --- Backtrack: 回溯 ---
          // 如果为 v 分配颜色 c 无法导向一个解，则撤销这次选择
          this.colors[v] = 0;
        }
      }
  
      // 如果尝试了所有颜色都无法为顶点 v 找到一个合法的方案，则返回 false
      return false;
    }
  
    /**
     * 主函数，启动回溯算法
     */
    solve() {
      // 从顶点 0 开始尝试着色
      if (this.solveColoringUtil(0)) {
        console.log(`成功找到一个使用 ${this.m} 种颜色的着色方案:`);
        this.printSolution();
        return true;
      } else {
        console.log(`无法使用 ${this.m} 种颜色为该图找到着色方案。`);
        return false;
      }
    }
  
    /**
     * 打印解决方案
     */
    printSolution() {
      const colorMap = ["", "红色", "绿色", "蓝色", "黄色", "紫色", "橙色"]; // 方便阅读
      const solution = this.colors.map((color, index) => 
          `顶点 ${index}: ${colorMap[color] || `颜色${color}`}`
      );
      console.log(solution.join('\n'));
    }
  }
  
  // --- 示例 ---
  // 假设有4个顶点，其连接关系如下：
  // 0 -- 1
  // | \  |
  // |  \ |
  // 2 -- 3
  const graphMatrix = [
    [0, 1, 1, 1], // 顶点0 连接到 1, 2, 3
    [1, 0, 1, 0], // 顶点1 连接到 0, 2
    [1, 1, 0, 1], // 顶点2 连接到 0, 1, 3
    [1, 0, 1, 0], // 顶点3 连接到 0, 2
  ];
  
  const m_colors = 3; // 尝试使用3种颜色
  
  console.log("--- 尝试使用3种颜色 ---");
  const coloringProblem1 = new GraphColoring(graphMatrix, m_colors);
  coloringProblem1.solve();
  
  console.log("\n" + "-".repeat(30) + "\n");
  
  // 尝试一个不可能的方案
  const m_colors_insufficient = 2; // 尝试使用2种颜色
  console.log("--- 尝试使用2种颜色 ---");
  const coloringProblem2 = new GraphColoring(graphMatrix, m_colors_insufficient);
  coloringProblem2.solve();

reference