当前课程知识点:Data Structures and Algorithm Design Part I >  06.Graph >  C.BFS >  06C-2

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

06C-2在线视频

下一节:06C-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

06C-2课程教案、知识点、字幕

所谓的广度优先遍历过程

可以大致描述为如下一段自然语言

具体来说 如果指定的起点是顶点s

那么这种搜索将首先访问s

在这个图中 我们通过将s染黑

表示它已经接受了访问

接下来我们需要访问

S所有尚未访问的邻接顶点

从这个图中来看

如果s具有若干个邻居

就需要逐一枚举

并且访问这些邻居

在这里由s通往它的那些

刚被访问的邻居的边都被加粗

这暗示着这些边都已经被我们的

算法所采纳和保留

这些边都是非常重要的

它们携带了整个遍历过程中

所发现的一些信息

我们很快就会看到

这些边将构成原图的一个

极大的无环子图

通常情况下是一棵树

或者是一个森林

反过来 在原图中

还会有一些边

我们并不采纳

比如在此时所有这些

刚被访问的节点之间

有可能也有连边

但是在经过广度优先遍历之后

它们将不再保留 而是被舍弃掉

接下来我们的关注点是

刚被访问的这些新发现的节点

我们将继续去枚举出

它们各自的所有邻接顶点

并且检查它们的状态

如果这些顶点中

仍有尚未访问者

就轮到对它们进行访问了

在这个图中 我们不妨

将这些新的顶点

画在图中的外围

也就是说 我们接下来将通过

刚刚被访问过的那些顶点

通往它们的边找到它们

同样地 在这些边中

也有一部分被我们保留下来

而另外一些则按照同样的原理

不予保留

再一次地 在新发现的这些顶点之间

也有可能连有某些边

比如说这些

而且这些边也同样地不会被

广度优先遍历所采纳

因此它们也没有加粗

好了 相对于这些

新近发现的顶点

在图中也就是这些

居于最外围的顶点

我们将再一次地去枚举出

它们所对应的邻居们

在图中 我们依然不妨

以更外围的一些顶点来示意

那么接下来也轮到

这些新发现的顶点

接受访问了

具体来说 我们也需要保留

若干由原先的顶点

通往新近访问这些顶点的边

而且同样地 尽管在这些顶点之间

也可能连有不同的边

我们也依然不予采纳

好 这个算法将不断地如此迭代反复

直到所有的顶点都接受了访问

仍以这幅图为例 我们可以看到

所谓广度优先搜索

的确是一种遍历

它会按照我们刚才

所介绍的那种策略

确定不同顶点接受访问的次序

并且按照这种次序

对各顶点逐个地访问

而整个搜索过程的最终产物或成果

不过是选自原图的一系列边

也就是这里加粗的这些边

而原图中其余的边

也就是这里用淡色细线条表示的边

都将被忽略

而不予进一步考虑

可以通过这个图看出

这里的取舍原则

也就是说 这里按照与起点s的距离

将所有的顶点划分为

若干个等价类

在这个图中 也就是一个套一个的环路

就像某些城市一样

可能有一环二环三环

以及诸如此类地 n环

那么在同一等价类内部

各顶点的边

都不会被采纳

而只有连接于相邻等价类之间的

某些边才会被采纳

请注意 同样是连接

相邻等价类顶点的边

未必都会被采纳

比如说这条 这条 这条 这条

以及这条 这条 这条和这条

而反过来 我们可以注意到

所有被保留下来

并且采纳的这些边

将足以把所有的顶点

连接起来

构成一个连通图

同时它们之间也因为刚才的规则

而不致于造成环路

也就是说 它是一个

极大的无环图

我们讲过 这就是一棵树

没错 它就是一棵树

因为这棵树中涵盖了

原图的所有的顶点

所以我们也称之为支撑树

Spanning Tree

另外 既然这样一个遍历过程

可以将所有的顶点划分为一个

一个又一个等价类

而且这些等价类

按照到起点s的距离

是逐次单调变化的

因此它与我们此前所介绍的

树的层次遍历

有异曲同工之妙

是的 对于图的特例

也就是树而言

这样一个遍历过程

其实就是不折不扣的层次遍历

所以反过来 我们也可以认为

所谓图的广度优先遍历

实际上就等同于

树的层次遍历

后者可以认为是前者的一个特例

而反过来 前者也是后者的推广

好了 那么这样一种

用自然语言描述的遍历过程

如何严格地描述为算法

并且实现为具体的代码呢?

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

06C-2笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。