编辑“︁图的着色问题”︁（章节）

== 算法设计 ==  
图的着色问题通常通过'''回溯法'''或'''分支限界法'''解决。以下是回溯法的实现步骤：  

1. **选择顶点顺序**：按某种策略（如最大度优先）选择顶点。  
2. **尝试着色**：为当前顶点尝试所有可能的颜色（不违反约束）。  
3. **递归验证**：若着色有效，递归处理下一个顶点；否则回溯。  
4. **终止条件**：所有顶点着色完成或颜色数超过当前最优解。  

=== 回溯法代码示例 ===  
以下是Python实现的回溯法解决图的着色问题：  
<syntaxhighlight lang="python">  
def is_safe(graph, colors, v, c):  
    """检查顶点v是否可以着色为c"""  
    for neighbor in graph[v]:  
        if colors[neighbor] == c:  
            return False  
    return True  

def graph_coloring_util(graph, k, colors, v):  
    """回溯法核心函数"""  
    if v == len(graph):  
        return True  # 所有顶点着色完成  
    for c in range(1, k + 1):  
        if is_safe(graph, colors, v, c):  
            colors[v] = c  
            if graph_coloring_util(graph, k, colors, v + 1):  
                return True  
            colors[v] = 0  # 回溯  
    return False  

def graph_coloring(graph, k):  
    """主函数：尝试用k种颜色着色图"""  
    colors = [0] * len(graph)  
    if graph_coloring_util(graph, k, colors, 0):  
        return colors  
    return None  

# 示例输入：图的邻接表表示  
graph = {  
    0: [1, 2],  
    1: [0, 2, 3],  
    2: [0, 1, 3],  
    3: [1, 2]  
}  
k = 3  # 颜色数  
result = graph_coloring(graph, k)  
print("着色结果:", result)  # 输出: [1, 2, 3, 1]  
</syntaxhighlight>  

=== 输入与输出解释 ===  
* **输入**：图的邻接表表示和颜色数 <math>k=3</math>。  
* **输出**：顶点着色列表，如 <code>[1, 2, 3, 1]</code> 表示顶点0颜色1，顶点1颜色2，依此类推。