基本信息

---

下载

文档摘要

---

2025年涂色算法面试题及答案

无向图k色着色判定问题

给定邻接表表示的无向图`graph`（其中`graph[i]`为节点`i`的所有相邻节点列表），节点编号为`0`到`n-1`。要求判断是否存在一种使用`k`种颜色的着色方式，使得任意相邻节点颜色不同。

解题思路：采用回溯法逐节点尝试颜色。从第0个节点开始，为每个节点选择一种颜色（1到k），确保该颜色与所有已着色的相邻节点颜色不同。若当前节点无法找到合法颜色，则回溯到前一节点更换颜色；若所有节点均成功着色，则返回`True`。关键优化点是剪枝：在为当前节点选择颜色时，仅保留与所有已着色邻居颜色不同的选项，减少无效递归。

代码实