Download presentation
Presentation is loading. Please wait.
1
DFS & BFS 2018年10月30日
2
树的定义： 树是由 根结点 和 若干棵子树 构成的。 （递归定义）
3
根节点 树的高度 1的子树 H=4 叶子结点：4，5，6，7，10，11，12 1的子节点为2，7，8 2的父节点为1 1 2 3 6 7
9 10 5 11 12 根节点 1的子树 树的高度 H=4 叶子结点：4，5，6，7，10，11，12 1的子节点为2，7，8 2的父节点为1
4
Depth-First-Search 深度优先搜索
5
DFS示例
6
求树的深度 1 2 3 6 7 4 8 9 10 5 11 12
7
遍历完整棵解答树之后，可以获得全局最优解
DFS的过程就是遍历一棵解答树的过程 每条到达叶子结点的路径代表一个可行解 遍历完整棵解答树之后，可以获得全局最优解 1 2 3 6 7 4 8 9 10 5 11 12
8
4053 素数环 给定一个整数N，请你将1,2,3...N组成一个首尾相接的环，使得任意两个相邻的数之和为素数。 请按字典序输出所有可能方案。若无合法方案请输出"None"。 由于数字组成的是一个首尾相接的环，规定输出时从1的位置开始按照顺时针输出。 例如: 输出为 输出为 枚举1到n全排列，检查是否符合条件
9
4053 素数环 剪枝
10
POJ 1088 滑雪（simplified） Michael喜欢滑雪这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。 Michael想知道从指定的一个点出发最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。
11
POJ 1088 滑雪（original） Michael喜欢滑雪这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。 Michael想知道在整个区域里最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。
12
POJ 1088 滑雪（original） 记忆化搜索
13
Breath-First-Search 广度优先搜索
14
从V0到V6至少需要几步才可以到达？ V0 V5 V4 V3 V2 V1 V6
15
从V0到V6至少需要几步才可以到达？ V0 V5 V4 V3 V2 V1 V6
16
从V0到V6至少需要几步才可以到达？ V0 V5 V4 V3 V2 V1 V6
17
从V0到V6至少需要几步才可以到达？ V0 V5 V4 V3 V2 V1 V6
18
从V0到V6至少需要几步才可以到达？ V0 V5 V4 V3 V2 V1 V6
19
思考： 如果不同的边的长度不一样，如何求V0到V6的最短路？ V0 V5 V4 V3 V2 V1 V6 1 2 1 2 1 1 3 4 3
20
队列 queue 先进先出 First-In-First-Out
21
BFS示例
22
POJ 2251 地牢大师 3 4 5 S.... .###. .##.. ###.# ##### ##.## ##... ####E 你被困在一个3D的地牢中，你需要尽快逃离地牢！地牢由l*r*c个单位立方格组成（），每次向上、下、东、南、西、北移动一格，均需要1分钟，部分立方格和地牢边缘都是实心的，无法通行。给出起点、终点和实心立方格的位置，请问是否能逃离地牢，能逃离的话最少需要多少时间？
23
POJ 2251 地牢大师
24
1994 二哥的地图 二哥最近拿到了一份世界地图，这个地图是一个N×M的矩阵，每个格子代表一块地方，有可能是陆地或者海洋，我们用0代表陆地，-1代表海洋。 这个地图并没有把国家标注出来，在强烈的好奇心的驱使下，二哥想知道这块地图上有最多可能有多少个国家。在这里，我们认为海洋不属于任何一个国家，每一块陆地属于且仅属于一个国家，并且相邻的陆地属于同一个国家。 3
25
DFS BFS
26
DFS 对应“栈” DFS 栈的最大容量不大于搜索树的深度 1 2 1 8 1 2 3 1 8 9 1 2 3 4 1 8 9 10
6 7 4 8 9 10 5 11 12 DFS 栈的最大容量不大于搜索树的深度 1 2 1 2 3 1 2 6 1 7 1 8 1 8 9 1 8 12 Time
27
BFS 对应“队列” BFS 队列的长度取决于每层节点数 2 7 8 7 8 3 6 8 3 6 3 6 9 12 6 9 12 4 5
10 5 11 12 BFS 队列的长度取决于每层节点数 Time 10 11
28
Pros & Cons 搜索树深度太深，DFS可能会导致爆栈，换用BFS。 搜索树宽度太大，BFS所需内存空间过大，换用DFS。
29
搜索树深度太深，DFS可能会导致爆栈，换用BFS。 搜索树宽度太大，BFS所需内存空间过大，换用DFS。
Pros & Cons 搜索树深度太深，DFS可能会导致爆栈，换用BFS。 搜索树宽度太大，BFS所需内存空间过大，换用DFS。 DFS代码简洁，所需空间更小，但速度较慢。 BFS代码较复杂，所需空间更大，但速度较快。
30
THANK YOU Q & A
Similar presentations
