地图着色问题：核心原理与 C++ 代码实现-育师

一、核心问题：一句话秒懂

地图着色的核心需求很简单：给地图上的所有区域着色，确保相邻区域（有公共边界，非点接触）颜色不同，同时使用最少的颜色。

关键结论（四色定理）：无论平面地图的区域如何划分，最多只需 4 种颜色就能满足 “相邻区域不同色” 的要求，这为我们的算法实现提供了明确的颜色数量上限。

二、问题简化：地图 → 图论模型转化

复杂的地图无法直接用代码处理，我们需要将其转化为计算机能理解的 “图论模型”，规则如下：

地图上的每个区域 → 图中的一个 “顶点”（用数字 0、1、2... 标识）；
两个区域相邻 → 图中对应的两个顶点之间连一条 “边”（用邻接矩阵标记）；
着色要求 → 有边连接的两个顶点（相邻区域）必须使用不同颜色。

简言之：地图着色问题 = 图的顶点着色问题（相邻顶点颜色不同）。

三、核心算法：回溯法（试错法）

对于中小规模地图（10-20 个区域），回溯法是最直观、易实现的算法，核心思路类似 “走迷宫试路”：

按顺序遍历每个顶点（区域）；
为当前顶点尝试分配 1-4 种颜色（符合四色定理）；
检查颜色是否合法（不与相邻顶点的颜色重复）；
若合法，继续处理下一个顶点；若不合法，换一种颜色尝试；
若所有颜色都尝试失败，回溯到上一个顶点，换颜色重新尝试；
直到所有顶点都着色完成，记录最少使用的颜色数。

四、精简 C++ 代码实现（可直接运行）

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_REGIONS = 10; // 最多支持 10 个区域 int adj_matrix[MAX_REGIONS][MAX_REGIONS] = {0}; // 邻接矩阵：1=相邻，0=不相邻 int region_color[MAX_REGIONS] = {0}; // 记录每个区域的颜色（0=未着色） int min_colors = MAX_REGIONS; // 最少颜色数（初始设为最大区域数） int region_count; // 实际区域总数 // 检查当前区域（cur）使用颜色（color）是否合法 bool is_color_valid(int cur, int color) { for (int i = 0; i < region_count; i++) { // 若相邻区域（adj_matrix[cur][i]=1）已使用该颜色，不合法 if (adj_matrix[cur][i] == 1 && region_color[i] == color) { return false; } } return true; } // 回溯函数：当前处理第 cur 个区域 void backtrack_color(int cur) { // 所有区域都着色完成，更新最少颜色数 if (cur == region_count) { int used_colors = 0; for (int c : region_color) { used_colors = max(used_colors, c); } min_colors = min(min_colors, used_colors); return; } // 尝试 1-4 种颜色（符合四色定理） for (int c = 1; c <= 4; c++) { if (is_color_valid(cur, c)) { region_color[cur] = c; // 分配颜色 backtrack_color(cur + 1); // 处理下一个区域 region_color[cur] = 0; // 回溯：撤销当前颜色分配 } } } int main() { // 示例：4 个区域（0-3）的相邻关系（可根据实际地图修改） region_count = 4; // 区域 0 与 1、2 相邻 adj_matrix[0][1] = adj_matrix[1][0] = 1; adj_matrix[0][2] = adj_matrix[2][0] = 1; // 区域 1 与 2、3 相邻 adj_matrix[1][2] = adj_matrix[2][1] = 1; adj_matrix[1][3] = adj_matrix[3][1] = 1; // 区域 2 与 3 相邻 adj_matrix[2][3] = adj_matrix[3][2] = 1; // 开始回溯着色 backtrack_color(0); // 输出结果 cout << "最少需要的颜色数：" << min_colors << endl; cout << "各区域的颜色分配（0=未着色，1-4=颜色编号）："; for (int i = 0; i < region_count; i++) { cout << region_color[i] << " "; } cout << endl; return 0; }

五、代码使用说明（小白也能会）

修改区域数量：将region_count设为你的地图实际区域数（≤10）；
设置相邻关系：通过adj_matrix[i][j] = 1标记区域 i 和 j 相邻（注意双向设置，如adj_matrix[0][1] = 1同时要adj_matrix[1][0] = 1）；
运行代码：直接编译运行，会输出 “最少颜色数” 和 “各区域颜色分配”；
扩展场景：若需要支持更多区域，修改MAX_REGIONS的值即可（如改为 20 支持 20 个区域）。