国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 019-dfs.bfs-图的遍历-《算法设计技巧与分析》M.H.A学习笔记

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

来源:程序员人生   发布时间:2016-07-14 14:44:59 阅读次数:2430次

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

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生