DFS及BFS的算法讲解(含例题)教学提纲.ppt

DFS BFS 蛋糕 相关理论 图的遍历 图是一种灵活的数据结构 一般作为一种模型用来定义对象之间的关系或联系 对象由顶点 V 表示 而对象之间的关系或者关联则通过图的边 E 来表示 图可以分为有向图和无向图 一般用G V E 来表示图 经常用邻接矩阵或者邻接表来描述一副图图的遍历就是从图中的某个顶点出发 按某种方法对图中的所有顶点访问且仅访问一次 为了保证图中的顶点在遍历过程中仅访问一次 要为每一个顶点设置一个访问标志 通常有两种方法 深度优先搜索 DFS 和广度优先搜索 BFS 再举一例完全二叉树练习三序遍历 DFS基本思想 基本步骤 1 从图中某个顶点v0出发 首先访问v0 2 访问结点v0的第一个邻接点 以这个邻接点vt作为一个新节点 访问vt所有邻接点 直到以vt出发的所有节点都被访问到 回溯到v0的下一个未被访问过的邻接点 以这个邻结点为新节点 重复上述步骤 直到图中所有与v0相通的所有节点都被访问到 3 若此时图中仍有未被访问的结点 则另选图中的一个未被访问的顶点作为起始点 重复深度优先搜索过程 直到图中的所有节点均被访问过 DFS的实现 基本框架 voidDFS PointP for 所有P的邻接点K if K未被访问 if k e returntrue 标记K dfs k 每次递归到一个点 则检查是否存在与它相邻 而且未被访问的点 有则递归访问这个点 无则返回上一层 BFS基本思想 BFS基本思想 基本框架 通常用队列 先进先出 FIFO 实现初始化队列Q Q 起点s 标记s为己访问 while Q非空 取Q队首元素u u出队 if u 目标状态 所有与u相邻且未被访问的点进入队列 标记与u相邻的点为已访问 两者比较 DFS类似于树的先根遍历 优先访问的是没有访问过的子节点 BFS类似于树的层次遍历 一层一层来访问 所以适合有目标求最短路的步数 DFS BFS多用于解决连通性问题及最短路问题 多数情况下运行BFS所需的内存会大于DFS需要的内存 DFS一次访问一条路 BFS一次访问多条路 但DFS容易爆 BFS通过控制队列可以很好解决 爆队列 风险 出栈次序 X星球特别讲究秩序 所有道路都是单行线 一个甲壳虫车队 共16辆车 按照编号先后发车 夹在其它车流中 缓缓前行 路边有个死胡同 只能容一辆车通过 是临时的检查站 如图 p1 png 所示 X星球太死板 要求每辆路过的车必须进入检查站 也可能不检查就放行 也可能仔细检查 如果车辆进入检查站和离开的次序可以任意交错 那么 该车队再次上路后 可能的次序有多少种 为了方便起见 假设检查站可容纳任意数量的汽车 显然 如果车队只有1辆车 可能次序1种 2辆车可能次序2种 3辆车可能次序5种 现在足足有16辆车啊 亲 需要你计算出可能次序的数目这是一个整数 请通过浏览器提交答案 不要填写任何多余的内容 比如说明性文字 典型例题 p1 png 油田 输入一个m行n列的字符矩阵 统计字符 组成多少个八连块 如果两个字符 所在的格子相邻 八个方向 就说明他们属于同一个八连块 如图 有两个八连块 典型例题 方格填数如下的10个格子 填入0 9的数字 要求 连续的两个数字不能相邻 左右 上下 对角都算相邻 一共有多少种可能的填数方案 请填写表示方案数目的整数 DFS 图的遍历 方格分割6x6的方格 沿着格子的边线剪开成两部分 要求这两部分的形状完全相同 如图 p1 png p2 png p3 png就是可行的分割法 试计算 包括这3种分法在内 一共有多少种不同的分割方法 注意 旋转对称的属于同一种分割法 请提交该整数 不要填写任何多余的内容或说明文字 剪邮票 如 图1 jpg 有12张连在一起的12生肖的邮票 现在你要从中剪下5张来 要求必须是连着的 仅仅连接一个角不算相连 比如 图2 jpg