基于深度优先的回溯算法框架

很多复杂点儿的问题都要用树或图来建模，树和图最基础的操作是遍历，但是有时候我们并不需要访 问每个结点。比如问你，中国地图上有镇江这个城市吗？那你肯定是找到就立马告诉我，而不会傻拉吧唧 地把每个城市都看一遍，即使找到了镇江也闷头向前。在这里我想为这一类问题提供一个算法的框架，降 低思维复杂度。

当然图的深度优先是基础，我在这里大概讲一下，读者有兴趣可以去看《算法导论》。图是由结点和 边组成的，深度优先的思想就是如果通过当前访问的结点还能跟踪到未访问的结点，那么就继续访问，这 也是“深度优先”这个名字的由来。按照这个描述，我们肯定要用变量来标识结点是否已经被访问，《算 法导论》用三种颜色 ——

白色： 还没被访问；

灰色： 即将被访问；

黑色： 已经访问过了，并且由此结点所跟踪到的结点也全都被访问过了。

我们每次访问一个结点时都问自己，现在是个什么状况？通常有以下三种 ——

好的，我已经能解决这个问题了： OK，直接返回就可以了，因为已经找到答案了；

还不能作出任何判断： 这样的话我们只能继续遍历咯；

虽然还不能对结果作出明确的判断，但是我们能确定后面结点无需再访问：回溯，然后返回。

于是深度优先的框架就出来了：

#define　WHITE　0
　　　　 #define　GRAY　1
　　　　 #define　BLACK　2
　　　　 #define　KNOWN　1　　　　　　　/*　已经能确定答案　*/
　　　　 #define　UNKOWN　2　　　　　　/*　一无所知　*/
　　　　 #define　CUT　3　　　　　　　　　/*　能确定可以剪枝　*/
　　　　 void　DFS(void)　{
　　　　　　　　 /*　最开始每个结点都没被访问　*/
　　　　　　　　 for　every　node　i　in　graph　{
　　　　　　　　　　　　 color[i]　=　WHITE;
　　　　　　　　 }
　　　　　　　　 /*
　　　　　　　　　 *要对每个结点都调用DFS_visit，
　　　　　　　　　 *这是为了处理非连通图。
　　　　　　　　　 *如果你已经能确定图是连通的，
　　　　　　　　　 *那么只要对一个结点调用DFS_visit就可以了
　　　　　　　　　 */
　　　　　　　　 for　every　white　node　v　in　graph　{
　　　　　　　　　　　　 if　(color[v]==WHITE)　　　　DFS_visit(v);
　　　　　　　　 }
　　　　 }
　　　　 void　DFS_visit(v)　{
　　　　　　　　 color[v]　=　GRAY;
　　　　　　　　 state　=　test(v);　//评估当前的状况
　　　　　　　　 if　(state==KNOWN)　{
　　　　　　　　　　　　 //do　something
　　　　　　　　　　　　 return　;
　　　　　　　　 }　else　if　(state==CUT)　{
　　　　　　　　　　　　 color[v]　=　BLACK;
　　　　　　　　　　　　 //　trace　back
　　　　　　　　　　　　 return;
　　　　　　　　 }
　　　　　　　　 for　every　node　u　adjacent　to　v　{
　　　　　　　　　　　　 if　(color[u]==WHITE)　　　　DFS_visit(v);
　　　　　　　　 }
　　　　　　　　 color[v]　=　BLACK;
　　　　　　　　 //　trace　back　
　　　　 }

你可以用这个框架去试着解决 POJ3740，或者自己去找些问题。如果发现此文错误请在此博客留言或 通过邮箱联系我。

出处：http://www.cnblogs.com/john-d/archive/2010/01/03/1638258.html