019-dfs.bfs-图的遍历-《算法设计技巧与分析》M.H.A学习笔记


深度优先搜索DFS

深搜框架:

bool dfs(int loc) {
标记状态loc已访问;
if (loc为目标状态) return true;
for (每一个可能的操作) {
对loc利用操作产生新状态nstat;
if (nstat合法且未被访问) {
if (dfs(nstat)) return true;
}
}
撤消loc已访问标记; // 这步要具体问题具体分析了
return false;
}

广度优先搜索BFS

实现方法

1. 首先将根节点放入队列中。

2. 从队列中取出第1个节点,并检验它是不是为目标。

· 如果找到目标,则结束搜索并回传结果。

· 否则将它所有还没有检验过的直接子节点加入队列中。

3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传找不到目标

4. 重复步骤2

广搜框架:

<pre name="code" class="cpp">bool bfs(int init) {
que.enque(init);
while (队列que不是空的) {
int loc = que.front(); que.deque();
if (loc是目标状态) return true;
for (每一个可能的操作) {
对loc利用操作产生新状态nstat;
if (nstat合法且未入队) {
标记nstat已入队;
que.enque(nstat);
}
}
}
return false;
}


补充:

简化代码:

在1类搜棋盘、搜地图、搜矩阵位置的问题中我们会频繁遇到“从当前点获得相邻点”的操作,为了缩短代码,我们可以开个方向数组dir[][2]表示方向,以4方向为例,则dir[4][2]
= {{0, 1}, {1, 0}, {0, 1}, {⑴, 0}};

用的时候有:

for (int i = 0; i < 4; ++i)
{
int newX = oldX + dir[i][0];
int newY = oldY + dir[i][1];
if (newX,newY均合法且未访问) // bfs或dfs的相干操作
}

记录路径:

广搜:

如果题目需要我们记录解路径,则对广搜有:

struct TStat{
int value;
int pre; // 记录其父状态在队列中的位置,初始化为⑴;
};

每次扩大新状态的时候令新状态的pre为当前状态在队列中的下标,待到达目标状态以后倒着查回第1个状态便可获得解路径。

深搜:

对深搜,则可另外开1个栈用来记录当前的合法状态,每次访问新状态前都压入当前状态到栈中,回溯时也相应地弹出栈顶,终究这个栈里将逆序记录解路径上的节点。大致做法以下:

stack<int> stk;
bool dfs(int loc) {
标记状态loc已访问;
stk.push(loc);
for (每一个可能的操作) {
对loc利用操作产生新状态nstat;
if (nstat合法且未访问) {
if (dfs(nstat)) return true;
}
}
stk.pop();
撤消loc已访问标记;
return false;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 019-dfs.bfs-图的遍历-《算法设计技巧与分析》M.H.A学习笔记

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡