图着色问题回溯法（最通俗易懂）

图着色问题描述：

对于给定无向连通图G=(V,E)，求至少用多少种颜色对G中的顶点进行着色，使得任意两个顶点的着色不同。

回溯法描述：

回溯法的本质其实就是一种蛮力法，只是通过一定的方法可以使得蛮力法中的一些基本情况可以提前排除从而提高蛮力算法效率，回溯可以理解为排除这些不满足条件的基本情况的过程。

图着色问题的求解算法：

①初始化颜色总数为无穷多种。
②每次从点集中选择一个顶点并从第一种颜色开始尝试对其进行着色；
③如果着色不冲突，则继续通过相同的方式处理点集中的下一个顶点；如果着色冲突，则说明该种着色方法行不通，退回到上一个结点，将上一个结点的着色改为当前着色的下一种颜色。
④重复上述过程，直到所有的顶点都着色为止，此时确定了一个可行解。如果可行解的颜色数少于当前颜色总数，则将颜色总数更新为可行解的颜色数。
⑤得到一个可行解后进行回溯，退回到上一个着色颜色序号小于当前颜色总数的结点上，将其着色改为下一种，并进行如上所示的推理过程。
⑥当存在一个结点没有颜色可以着色时，算法停止。当前最优解即全局最优解。

图着色问题的求解实例：

（无向图如下所示，颜色用a,b,c…进行表示）

①给顶点A着色a，由于是第一个顶点，所以一定不发生冲突。
②给顶点B着色a，和A顶点发生冲突，因此换为下一种颜色b，此时不发生冲突，因此最终给B着色b。
③给顶点C着色a，和A顶点发生冲突；给顶点C着色b，和B顶点发生冲突，因此给C顶点着色下一种颜色c，此时不发生冲突，因此最终给C着色c。
④给顶点D着色a，不发生冲突，因此最终给D着色a。
⑤给顶点E着色a，与D发生冲突；给顶点E着色b，与B发生冲突；给顶点E着色c，与C发生冲突，给顶点E着色下一种颜色d，此时不发生冲突，因此最终给E着色d。
此时所有顶点都完成着色，也就是确定了一个可行解（abcad，4种颜色），开始回溯过程。
⑥回到顶点D，由于其在上一个可行解中着色为a，因此本次对其着色为a的下一种颜色b，与B发生冲突，因此将其着色为再下一种颜色c，此时不发生冲突，因此最终将其着色为c。
⑦给顶点E着色a，不发生冲突，因此最终将顶点E着色为a。再次得到一组可行解（abcca，3种颜色）。由于该可行解使用的颜色比上一组可行解更少，因此将最优解更新为3。
⑧进行回溯：由于结点C和D的着色都是当前3种颜色中序号最大的颜色c，因此回溯到B结点，将其着色改为c。
⑨对C结点着色c，与B结点冲突，想要换为下一种颜色，但是当前只有3种颜色，因此判断算法终止，全局最优解即为3种颜色。