当前课程知识点：数据结构（Data Structures） > 6. Graph > 6.6 Graph Traversal - BFS > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
接下来的课程中我们将学习到
图的另外一种常见的遍历操作
广度优先查找
从字面上去理解
广度优先查找它的这个遍历方法
和深度优先查找是完全不同的
遍历的过程是一种横向扩展的过程
我们以下面这张图为例子
来讲解一下这个过程
首先我们从A出发开始这个遍历过程
我们将首先访问A顶点
然后接下来我们将依次访问A的所有
未访问过的邻居顶点
这一点和深度优先遍历是完全不一样的
在DFS中
我们是选择一个没有访问过的邻居
然后就继续的深度优先访问下去
但是在BFS中
是要所有没有访问过的邻居都一起来访问
在访问完A的邻居之后
接下来再去继续访问
所有没有访问过的A的邻居的邻居
这个过程有点类似于地毯式的搜索过程
从某一个点出发
然后由近及远的一层一层往外进行访问
为了能够组织这个由近及远的
有层次的访问过程
我们可以借助一个队列
来去记录整个访问过程中
我们所接触过的顶点
比如在这个例子中
我们是从A顶点开始进行访问
所以在访问完A之后
我们把它记录在队列中
接下来的过程我们应该去访问
A的所有没有访问过的邻居顶点
所以我们可以从队列中把A取出来
然后去访问A的所有没有访问过的邻居
并且把它们加入到队列中去
接下来的过程我们需要去访问
队列中的这些已经访问过的顶点
它们的邻居顶点
所以我们从队列中继续取出一个顶点C
然后去访问C的所有没有访问过的邻居
并且把它们加入到队列中去
类似的过程不断地持续下去
每次我们都是从队列中
取出一个已经访问过的顶点
然后去访问它的没有访问过的邻居
并且把这些邻居顶点也加入到队列中去
这个过程持续的迭代
直到队列变成空的时候遍历过程就结束了
整个过程中我们可以看到
总是去访问完某个顶点的
所有没有访问过的邻居之后
就把它们放入到队列中去
然后再去访问其它顶点的邻居
这就体现了广度优先遍历的思想
下面我们来看一下
基于队列的BFS过程它的代码实现
这里面BFS函数它有三个参数
第一个是图的指针 G
第二个start它是遍历的出发顶点
我们将从start开始进行遍历操作
第三个参数是一个队列的指针 Q
这个队列用来去辅助我们的遍历操作
我们首先要做的事情是先去访问顶点start
然后把start加入到队列中去
接着我们通过一个循环迭代
来去执行这个遍历操作
只要队列Q它不是空的
我们将从队列中取出一个顶点
然后我们将访问这个顶点的
所有没有访问过的邻居顶点
所以我们这里用到一个循环语句
其中这个w取遍v的所有邻居
对每个v的邻居w
我们首先判断一下w是否已经访问过
如果没有访问过
我们就去访问这个邻居顶点
并且在访问完之后把w加入到队列中去
这个循环的过程不断地持续进行
直到队列变成空的
这个时候图上的
从顶点start出发可以到达的所有顶点
我们都已经访问完毕了
并且每个顶点只访问了一次
在BFS的过程中我们访问过的顶点和连边
连接在一起将会构成一棵树
这棵树我们称为叫BFS树
广度优先查找树
BFS树是图中的一个连通之图
它刻画了BFS整个访问的轨迹
好 我们这节课就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
