019-dfs.bfs-图的遍历-《算法设计技巧与分析》M.H.A学习笔记
来源：程序员人生 发布时间：2016-07-14 14:44:59 阅读次数：2461次
深度优先搜索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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
