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

发布时间：2020-12-13 21:11:39 所属栏目：PHP教程来源：网络整理

导读：深度优先搜索DFS 深搜框架: bool dfs(int loc) { 标记状态loc已访问; if (loc为目标状态) return true; for (每一个可能的操作) { 对loc利用操作产生新状态nstat; if (nstat合法且未被访问) {if (dfs(nstat)) return true; } } 撤消loc已访问标记; // 这步要

深度优先搜索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,{⑴,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; }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!