迷宫寻址中深度优先搜索的递归和非递归算法比较

    巧若拙（欢迎转载，但请注明出处：http://blog.）

    本文只探究迷宫寻址中深度优先搜索的递归和非递归算法比较，其他相关代码详见《迷宫问题（巧若拙）》http://blog.

    深度优先搜索的递归算法是很容易实现的，只需设置一个驱动函数，然后递归调用子函数就可以了。
代码如下：
int DeepSearchWay()//寻找路径：深度搜索
{
    CopyMiGong();
      
    if (c_map[begin[0]][begin[1]] == OPEN && Search(begin[0], begin[1]))
    {
        c_map[begin[0]][begin[1]] = ROAD;
        return true;
    }
        
    return false;
}

int Search(int x, int y)//深度搜索递归子函数
{
    int i;

       c_map[x][y] = PASSED;  
    if (IsEnd(x, y)) //找到出口
    {
        c_map[x][y] = ROAD;  
        return true;
    }
      
    for (i=0; i<4; i++)//判断当前路径点四周是否可通过
    {
        if (c_map[x+zx[i]][y+zy[i]] == OPEN && Search(x+zx[i], y+zy[i]))
        {
            c_map[x][y] = ROAD;
            return true;
          }
   }
   return false;
}



深度优先搜索的非递归算法需要人工设置一个栈，把搜索过的点存储到栈中，走不通的点就退栈，找到出口就退出函数。
代码如下：
int DeepSearchWay_2()//寻找路径：深度搜索
{
    int x, y;
    int top = 0; //栈顶指针
    int sum = 0;//累积搜索过的点数量

    CopyMiGong();
    way[0].x = begin[0];
    way[0].y = begin[1];
    way[0].pre = 0;
    c_map[way[0].x][way[0].y] = PASSED; //该点已走过

    while (top >= 0)
    {
          if (way[top].pre < 4)
          {
            x = way[top].x + zx[way[top].pre];
            y = way[top].y + zy[way[top].pre];

            if (c_map[x][y] == OPEN)//如果某个方向可通过，将该点纳入栈
            {
                sum++;
                top++;
                way[top].x = x;
                way[top].y = y;
                way[top].pre = 0;
                c_map[x][y] = PASSED;
               
                if (IsEnd(x, y)) //找到出口
                {
                    PutStack(top); //把栈路径显示到迷宫中
                    printf("\n深度优先搜索可行路径，总共搜索过%d个点\n", sum);
                    return true;
                }
            }
            else  //否则换个方向
                way[top].pre++;
        }
        else
        {
               top--;
           }
    }
    return false;
}

void PutStack(int top) //把栈路径显示到迷宫中
{
    CopyMiGong();

       while (top >= 0)
    {
        c_map[way[top].x][way[top].y] = ROAD;
        top--;
    }
}

深度优先搜索最短路径，除了存储当前遍历结点的栈以外，需要额外设置一个栈存储最短路径。为了避免重复搜索某顶点，我为各个顶点设置了路径长度，只有当前路径长度小于原来的路径长度时，才搜索该顶点。
找到出口后并不退出函数，若当前路径长度小于最小路径长度，则更新最小路径长度，否则直接退栈进入上一点，继续搜索。
直到所有可能的路径被搜索完毕，输出最短路径。
代码如下：
int DeepSearchWay_3()//寻找路径：深度搜索（最短路径）
{
    int x, y, i, j;
    int top = 0; //栈顶指针
    int pathLen[M+2][N+2] = {0};
    struct stype shortWay[M*N];
    int flag = false; //标记是否能到达终点  
    int sum = 0;//累积搜索过的点数量
   
    for (x=0; x<M+2; x++) //设置各点初始路径长度均为最大值
        for (y=0; y<N+2; y++)
            pathLen[x][y] = MAXLEN;

    CopyMiGong();
    minLen = MAXLEN;  //最短路径
    way[0].x = begin[0];
    way[0].y = begin[1];
    way[0].pre = 0;
    pathLen[begin[0]][begin[1]] = 0;

    while (top >= 0)
    {
          if (way[top].pre < 4)
          {
            x = way[top].x + zx[way[top].pre];
            y = way[top].y + zy[way[top].pre];

            if (c_map[x][y] == OPEN && pathLen[x][y] > top+1)//如果某个方向可通过，且为最短路径，将该点纳入栈
            {
                sum++;
                top++;
                way[top].x = x;
                way[top].y = y;
                way[top].pre = 0;
                pathLen[x][y] = top;
                if (IsEnd(x, y)) //找到出口
                {
                    if (top < minLen)
                    {
                        minLen = top;
                        for (i=0; i<=top; i++)
                        {
                            shortWay[i] = way[i];
                        }
                        
                    }

                    flag = true;
                    top--;
                }
            }
            else  //否则换个方向
                way[top].pre++;
        }
        else
        {
               top--;
           }
    }
   
    if (flag)
    {
        for (i=0; i<=minLen; i++)
        {
            way[i] = shortWay[i];
        }
        PutStack(minLen); //把栈路径显示到迷宫中
    }
   
    printf("\n深度优先搜索最短路径，总共搜索过%d个点\n", sum);
        
    return flag;
}