当前课程知识点:Data Structures and Algorithm Design Part I > 06.Graph > C.BFS > 06C-5
返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part I》慕课在线视频列表
以下我们就以这幅无向图为例
具体地了解
整个广度优先搜索的详细过程
请注意 这里首先引入了
一个初始为空的队列
我们的起点不妨取作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剔除掉
转入这样一种形式
整个遍历的最终产物是一棵遍历支撑树
至此
对这个性质和结论
你应该不存任何质疑了吧?
-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
-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
-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
-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
-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
-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
-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
-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