DFS及BFS的算法讲解（课堂PPT）

1、1 12 2蛋糕3 3l图是一种灵活的数据结构，一般作为一种模型用来定义对象图是一种灵活的数据结构，一般作为一种模型用来定义对象之间的关系或联系。对象由顶点（之间的关系或联系。对象由顶点（V）表示，而对象之间的关）表示，而对象之间的关系或者关联则通过图的边（系或者关联则通过图的边（E）来表示。图可以分为有向图和）来表示。图可以分为有向图和无向图，一般用无向图，一般用G=(V,E)来表示图。经常用邻接矩阵或者邻接表来表示图。经常用邻接矩阵或者邻接表来描述一副图图的遍历就是从图中的某个顶点出发，按某种方来描述一副图图的遍历就是从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。为了保

2、证图中的顶点法对图中的所有顶点访问且仅访问一次。为了保证图中的顶点在遍历过程中仅访问一次，要为每一个顶点设置一个访问标志在遍历过程中仅访问一次，要为每一个顶点设置一个访问标志。通常有两种方法：深度优先搜索。通常有两种方法：深度优先搜索(DFS)和广度优先搜索和广度优先搜索(BFS)4 45 5再举一例完全二叉树再举一例完全二叉树 练习三序遍练习三序遍历历6 6基本步骤：7 7基本框架void void DFSDFS( ( PointPoint P ) P ) for( for(所有所有P P的邻接点的邻接点K)K) if(K if(K未被访问未被访问) if(k = = e) if(k = =

3、 e) returnreturn true; true; 标记标记K;K; dfs( dfs(k);k); 每次递归到一个点，则检查每次递归到一个点，则检查是否存在与它相邻，而且未是否存在与它相邻，而且未被访问的点，有则被访问的点，有则递归递归访问访问这个点，无则返回上一层。这个点，无则返回上一层。8 89 91010基本框架通常用队列通常用队列( (先进先出先进先出, ,FIFOFIFO) )实现实现初始化队列初始化队列Q.Q.Q=Q=起点起点s; s; 标记标记s s为己访问为己访问; ;whilewhile (Q (Q非空非空) ) 取取Q Q队首元素队首元素u; uu; u出队出队;

4、;if if (u = (u = 目标状态目标状态) ) 所有与所有与u u相邻且未被访问的点进入队列相邻且未被访问的点进入队列; ;标记与标记与u u相邻的点为已访问相邻的点为已访问; ; 1111DFS类似于树的先根遍历，优先访问的是没有访问过的子节点；BFS类似于树的层次遍历，一层一层来访问，所以适合有目标求最短路的步数；DFS/BFS多用于解决连通性问题及最短路问题;多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路，BFS一次访问多条路)，但DFS容易爆，BFS通过控制队列可以很好解决爆队列风险1212 X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，

5、共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。 路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。 X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。 如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？ 为了方便起见，假设检查站可容纳任意数量的汽车。 显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。 现在足足有16辆车啊，亲！需要你计算出可能次序的数目这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性文字）。 13131414输入一个m行

6、n列的字符矩阵，统计字符“”组成多少个八连块。如果两个字符“”所在的格子相邻（八个方向），就说明他们属于同一个八连块。如图，有两个八连块 * * * * * * * * * * * * 1515方格填数 如下的10个格子,填入09的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的整数。 1616方格分割 6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图：p1.png, p2.png, p3.png 就是可行的分割法。试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。请提交该整数，不要填写任何多余的内容或说明文字。1717如【图1.jpg】, 有12张连在一起的12生肖的