当前课程知识点：数据结构 > 第6章 图 > 6.3 遍历 > 讲解（下）
现在，我们来看第二种遍历方式
广度优先搜索
简称BFS
它首先访问给定的起始顶点v
然后，去访问v的所有邻居
注意这地方，是所有，不像我们刚才深度优先搜索那样，是访问第一个邻居
v的所有邻居访问完了之后，去访问它的第一个邻居w的所有邻居
然后，访问v的下一邻接点x的所有邻居
w和x都是v的邻居
我们给出一个无向图
从起始顶点1开始
访问1之后，访问1的所有邻居2和3
然后，再去访问1的第一个邻居
2的所有邻居，也就是4和5
然后，去访问1的第二个邻居
3的所有邻居，6和7
然后，访问4的邻居8
这样，所有的8个顶点都访问完毕了
再来看一个有向图
同样，从1开始，1到2，1到3，2到4，注意，2的邻居已经访问完了，2是到不了5的
然后，从3开始，3到6
3到7
然后
4的邻居，4到8
再看6的邻居，7已经被访问过了，7的邻居都被访问过了
现在，还剩5没有访问
但是，从1是走不到5的，从其它顶点都走不到5
我们要处理这种极端的情况
5顶点是访问不到的
通过刚才的两个例子
我们可以看出，图的广度优先搜索，跟前面的树的层次遍历差不多
在前面
我们只是提了一下
树有层次遍历
但是，我们没有给出具体的算法
它的结果，是比较容易写出来的
因为，是从上到下
从左到右
这跟我们人去遍历一个非线性的结构，所采用的思维
通常是一致的
如果要用算法来实现
它的思想，就跟我们现在讲的广度优先搜索是类似的
现在，我们给出内存当中的邻接矩阵和邻接表，来写出广度优先搜索它的结果
这里先采用邻接矩阵
我们不看这个图
我们直接看内存当中的结构
从A开始
去找这一行
有两个下标是1
1和2
也就是B和C
那我们访问完A之后，访问A的邻居B、C
然后，从第一个邻居开始
也就是这一行，发现有两个1
这个1已经访问过了，这个1
是下标为3的，也就是D
所有顶点都访问完毕
现在，我们再来看邻接表
从A开始
两条边，下标分别是1和2
就是B和C
A到B
到C，B和C是A的邻居
然后，从B开始
这条边已经被访问过了
这条边，3，也就是D
去访问D，所有的顶点都访问完了
我们通过刚才给出的算法思想，会发现，它是优先访问所有的邻接点
是把当前顶点的所有邻接点都访问完了之后，再去访问邻接点的所有邻接点
每一层最后一个顶点被访问后，应回到该层的第一个顶点
假设A
它的B、C、D
三个邻居都访问完了
紧接着，应该去访问B的
所有邻居，也就是说，某一层最后一个顶点
被访问完了
应该回到该层的第一个顶点
以便去找它的所有邻居
还有，先被访问的顶点
它的邻接点，比后被访问的顶点的邻接点，先访问
比如，我们回到刚才这个图
你会发现
2和3，作为1的邻居，2比3要先访问
然后，2的邻居4和5，要比3的邻居6和7，要先访问
4、5比6、7先访问
这是因为2比3先访问
而4、5是2的邻居
6、7是3的邻居
我们写出这样一句话
是为了告诉大家
又看到了先...先...
很明显
我们应该想到队列
我们可以使用队列，暂存当前访问的顶点
以便后面某一层的顶点访问完毕之后，再从队列当中，取出这一层的第一个顶点
现在，我们给出完整的算法实现
同样，引入一个辅助的数组
标志某一个顶点是否被访问过了
访问以邻接矩阵表示的图G
以广度优先搜索来访问
首先
我们初始化一个队列
然后，开始循环
对每一个顶点进行循环
这是因为，有些顶点是无法经过其它顶点走到的
如果v没有被访问过
那么访问v，将访问标志置成1
别忘了，将v入队
因为，将来我们会从队列当中，取出这个v
以便去找它的邻居
所以，在访问完v之后，应该紧接着将它入队
下面我们要做的事情
就是判断队列Q是否为空
如果不为空
我们取出队头
将队列Q的队头元素删除
出队，放到u里面
然后，去找u的所有邻居
这个伪码
跟刚才
DFS是一样的
总之
把一个顶点的所有邻居都找到
直到它没有未被访问过的邻居
如果w没有被访问过
那么
访问它，修改成1，入队
这就是完整的算法
它的时间复杂度
跟刚才深度优先搜索是类似的，邻接矩阵
我们总要处理n^2个元素，而邻接表
总要处理
n个头结点以及e个边结点
空间复杂度，因为这里用到了一个容量跟
图当中顶点数一样的队列Q
所以，它的空间复杂度
也是n
现在，我们来对比一下深度优先搜索和广度优先搜索
从名字上来看，一个是深度
一个是广度
一个是尽量地先往纵深去访问
另一个，是先把最近的邻接点都访问完了
再去往前走
找到第一个邻居的所有的邻居
如果我们用现实生活当中的例子来讲
深度优先搜索就类似于走迷宫
而广度优先搜索
就类似于摸眼镜
我们先看走迷宫
走迷宫
实际上，就是用穷举、用试探
假设，绿色的是给定的起始顶点
我们随便沿着一个方向
比如，我们先往上
往上走
只要上方向能走
我们就走
直到走不动
我们就换一个方向
迷宫就是这样来求解的
它就是深度优先
我去找邻居
邻居如果还有未被访问的邻居
我就继续找，一直往纵深去找
而广度优先
就类似于摸眼镜
如果眼镜掉在地上了
我们去找
我们先是找离我最近的
就是手能够摸到的那个半径范围内的
我全摸一遍
就是把我当前站在这个位置
所有的邻近的位置，全都摸一遍
如果没有，我再去往前走一步
再去摸邻近的
所有的那个半径
这就是广度优先搜索
采用BFS
这种思想来求解问题
我们会发现，它首先找到的解，一定是最优解，或者说最近解
而DFS则不一定
比如，对于同样的迷宫
左边的DFS和右边的BFS，都能找到最后的出口
但是，如果迷宫还存在另外的出口
也就是问题有多个解
假设，迷宫的左下角也有一个出口
你会发现
BFS
它首先找到这个出口
然后，再找到这个出口
而DFS则不一定
我们先看BFS
由于BFS是优先去找离自己最近的那些邻居
然后，再找到第一个邻居
从它开始，再去找它最近的邻居
所以，它一定会首先探测到离入口最近的这个出口
而DFS
由于你采用的探测方向
不是固定的，或者说，是事先约定的
比如，我们事先约定，先朝着上方向走
只要上方向能走
我就一直朝着上方向走
如果走到了某一个位置
发现，它再往上走不了了
这时候，我才切换方向
不撞南墙不回头
但是，下一个切换到哪个方向呢
你可以约定
沿着上、右、下、左的这个顺序，来切换方向
你也可以约定，沿着上、左、下、右的方向来切换
所以，DFS
找到这两个解
它们的先后顺序，是不固定的
它跟你的初始方向以及切换方向(切换顺序)是有关的
比如，我们采用图当中的这种初始方向和顺序
那么，它首先找到的是这个出口
然后，再找到这个出口
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
