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

Love The Way You Lie 2021-11-29 12:38 226阅读 0赞

作者： John Waken  
邮箱:  JohnWaken@163.com  
转载请著明： http://www.cnblogs.com/john-d/admin/EditPosts.aspx?postid=1638258  
  
  
很多复杂点儿的问题都要用树或图来建模，树和图最基础的操作是遍历，但是有时候我们并不需要访问每个结点。比如问你，中国地图上有镇江这个城市吗？那你肯定是找到就立马告诉我，而不会傻拉吧唧地把每个城市都看一遍，即使找到了镇江也闷头向前。在这里我想为这一类问题提供一个算法的框架，降低思维复杂度。  
  
当然图的深度优先是基础，我在这里大概讲一下，读者有兴趣可以去看《算法导论》。图是由结点和边组成的，深度优先的思想就是如果通过当前访问的结点还能跟踪到未访问的结点，那么就继续访问，这也是“深度优先”这个名字的由来。按照这个描述，我们肯定要用变量来标识结点是否已经被访问，《算法导论》用三种颜色 ——  
    白色： 还没被访问；  
    灰色： 即将被访问；  
    黑色： 已经访问过了，并且由此结点所跟踪到的结点也全都被访问过了。  
  
我们每次访问一个结点时都问自己，现在是个什么状况？通常有以下三种 ——  
    好的，我已经能解决这个问题了： 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，或者自己去找些问题。如果发现此文错误请在此博客留言或通过邮箱联系我。

转载于:https://www.cnblogs.com/john-d/archive/2010/01/03/1638258.html