首页 > 代码库 > 迷宫寻址中深度优先搜索的递归和非递归算法比较
迷宫寻址中深度优先搜索的递归和非递归算法比较
迷宫寻址中深度优先搜索的递归和非递归算法比较
巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）
本文只探究迷宫寻址中深度优先搜索的递归和非递归算法比较，其他相关代码详见《迷宫问题（巧若拙）》http://blog.csdn.net/qiaoruozhuo/article/details/41020745
深度优先搜索的递归算法是很容易实现的，只需设置一个驱动函数，然后递归调用子函数就可以了。
代码如下：
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)//深度搜索递归子函数
{
inti;
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()//寻找路径：深度搜索
{
intx, 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()//寻找路径：深度搜索（最短路径）
{
intx, y, i, j;
int top = 0; //栈顶指针
int pathLen[M+2][N+2] = {0};
struct stype shortWay[M*N];
intflag = false; //标记是否能到达终点
intsum = 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;
}
迷宫寻址中深度优先搜索的递归和非递归算法比较