Given an undirected graph G=(V,E), it is required to color each vertex in V with one of three colors, say 1,2, and 3, such that no two adjacent vertices have the same color.
首先抛弃数据结构中所学到的树以及二叉搜索树等概念，在算法中的搜索树的节点常常用来表示某个处理阶段所处的状态。以3着色问题为例，讲解搜索树。
如图中的无向图所示，现需要用3个颜色对顶点进行着色，但要求相邻节点的颜色不一样，那么该问题的所有可能的解可以用一个搜索树来表示，如下
其中根节点代表初始状态，没有颜色填充，第二行节点代表第一个节点被填充的颜色的所有可能，第三行表示第二个节点被填充的所有颜色，不管是否符合要求，都要一一列举出来。
显然这类求解方式的时间复杂度为指数级别的，3着色问题的时间复杂度为 O ( 3 n ) O(3^n) O(3n)
接下来进入正题部分，回溯法为了避免搜索树将所有可能性全部列出来而残生的，根据要求及时检查，符合要求继续深度搜索，反之回溯。
具体的步骤如下：
1.如果搜索树没有搜索到底部(或者定义搜索树深度为n，搜索深度小于n)，并且当前节点符合要求，那么继续向下搜索。
2.如果搜索深度小于n，当前节点不符合要求，回溯到上一个节点搜索。
3.如果搜索深度==n并且当前节点符合要求，那么找到正确的解并输出。
4.如果搜索完所有节点都没有成功，那么搜索失败，问题无解。
针对3着色问题，原版论述如下：
存在回溯过程，复杂度变为 O ( n 3 n ) O(n3^n) O(n3n)，但是实际效果却比搜索树中 O ( 3 n ) O(3^n) O(3n)要好得多。
#include<iostream> using namespace std; #define colornum 3 #define vecnum 5 bool flag; //检查添加的颜色是否符合要求 bool check(int g[][5],int* color,int k){ for(int j=0;j<vecnum;j++){ if(g[k][j]==1&&color[j]==color[k]){ return false; } } return true; } void dfs(int g[][5],int* color,int k){ if(k==vecnum){//搜索完最后一个节点，输出结果%节点号:颜色 for(int i=0;i<vecnum;i++) cout<<i<<":"<<color[i]<<endl; flag=true; return; } for(int i=1;i<=colornum;i++){ color[k]=i; if(check(g,color,k)&&k<vecnum){ dfs(g,color,k+1); if(flag)return;//发现结构及时return } } return; } int main(){ //图结构 int g[vecnum][vecnum]={0,1,1,0,0,1,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,1,0}; //存储节点颜色1,2,3 int color[vecnum]={0}; flag=false;; dfs(g,color,0); if(flag==false) cout<<"cannot find result\n";//搜索失败 }