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

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

06C-5 在线视频

下一节:06C-6

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

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

以下我们就以这幅无向图为例

具体地了解

整个广度优先搜索的详细过程

请注意 这里首先引入了

一个初始为空的队列

我们的起点不妨取作s

按照算法的流程 首先令s入队

并且同时将它标记为discovered(误)的状态

在这里 我们依然用深色

来表示处于这种状态的顶点

接下来将逐一地枚举s的邻居

也就是a c和d

它们都是白色

也就是处于最初的undiscovered的状态

因此它们都会被取出并且归入队中

请注意 关于同一顶点的所有邻居

我们这里并没有定义一个优先次序

实际上 这并不是什么实质的问题

你完全可以根据自己的偏好

采用某种策略 甚至是随机的策略

比如这里不妨以它们的ID

也就是字母编号为序

同样地 在这些顶点依次入队的同时

它们也会从最初的undiscovered的状态

转化为discovered的状态

这也是为什么在这个时刻

它们会进而转为深色

每个邻居状态转化的同时

都会生成一条tree edge

在所有相关的tree edge悉数生成之后

s也就完成了它的历史使命

它将会被标记为visited 也就是最终的状态

相应地 在图中这个顶点

改为双边框的形式以示区别

接下来 应该是当前的队首节点a出队

我们可以看到 在a出队之后

也同样需要遍历它的所有的邻居

其中s是它的父亲 所以直接忽略掉

而c已经被发现 处于discovered状态

这种情况应该是属于算法的else那个分支

也就是说 对c不做任何处理

而是将由a通往c的这条边标记为CROSS

也就是跨边

再接下来 a的下一个邻居e

在当时仍处于最初的undiscovered状态

这是属于算法流程的if那个分支

所以令e入队并且同时转为discovered的状态

在图中变成深色

好 接下来

又该轮到新的队首顶点c出队

c出队之后也需要环顾四周

首先忽略掉它的父亲s

以及已处于visited状态的a

实质需要考虑的只有

仍处于最初undiscovered状态的顶点b

所以令b入队并且同时转为discovered的状态

至此既然c的所有邻居都已处理完毕

它也顺利地转入最终的visited的状态

接下来 新的队首节点d同样会出队

而且站在d的角度 环顾它的所有邻居

忽略掉它的父亲

唯一的邻居b已经入队 处于discovered的状态

所以在这里无需做任何实质操作

而只需将由d通往b的这条边

标记为跨边CROSS

同样在此之后 d也将顺利地转入

最终的visited的状态

算法的焦点又进而转至新的队首顶点e

再一次地 站在顶点e的角度

环顾它的所有邻居

忽略掉它的父亲a

另外两个邻居f和g

都是处于最初undiscovered的状态

所以这也是属于算法的if分支

因此令这两个新发现的邻居依次入队

并且同时标记为discovered的状态

此后

e自己也顺利地转入最终的visited状态

综观全局 你就会发现

此时已经没有任何顶点

依然处于最初的undiscovered状态

所以接下来只不过是一系列的过门

可能会标记出一些cross edge

但是不再会有新的tree edge生成

所以经过若干过门之后

最终必然会转入这个状态

也就是说

所有的顶点经过入队之后都已出队

而且相应地 都已转化为最终的visited状态

此时如果忽略掉所有的cross edge

那么剩下的tree edge就的确构成了一棵树

如果你对这个还看得不是很清楚

不妨把cross edge剔除掉

转入这样一种形式

整个遍历的最终产物是一棵遍历支撑树

至此

对这个性质和结论

你应该不存任何质疑了吧?

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-5 笔记与讨论

也许你还感兴趣的课程:

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