考虑3着色问题：

给出一个无向图G=(V,E)，需要用三种颜色之一为V中的每个顶点着色，三种颜色分别为1，2和3，使得没有两个邻接顶点有相同的颜色。把这样的着色成为合法的；否则，如果两个邻接的顶点有同一种颜色就是非法的。

一种着色可以用n元组(c1,c2,…,cn)来表示，使ci∈{1,2,3}，1≤i≤n。例如，(1,2,2,3,1)表示一个有5个顶点的图的着色。

一个n个顶点的图共有3^n种可能的着色（包括合法的和非法的），所有可能的着色的集合可以用一棵完全的三叉树来表示，称为搜索树。在这棵树中，从根到叶节点的每一条路径代表一种着色指派。

👇对于一个有三个顶点的图的所有可能3着色的搜索树

如果没有两个邻接的着色顶点有同样的颜色，图的一个不完全着色称为部分解。回溯法通过每次一个节点地生成基底树来工作。如果从根到当前节点的路径对应一个合法着色，过程就终止（除非想要找到不止一种着色方式）。

考虑下图a👇，考虑用颜色{1,2,3}对其顶点着色，图b👇是在搜索一个合法的着色的过程中生成的搜索数的一部分。

注意：