今天是周日，大家都干嘛去了？老实交代……
叫兽今天去看了《一步之遥》，感想是什么？不仅是什么马走日，项走田。还联想到59分和60分这“一步之遥”，呵呵。
今天我们来复习图的深度遍历和广度遍历
所谓图的深度优先遍历，是指从图的某一顶点V出发，访问此顶点；然后依次从V的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。
对一个图进行的深度优先遍历过程如下：
在遍历前，为图设置一个访问标志数组visited[n]，它只有0和1两个值。未遍历的点对应下标的值设为0，已遍历的点对应下标的值设为1。
然后，任意选择一个顶点开始访问
然后访问它的一个没有访问过的邻接点（对应下标的值为0）
若被访问过的顶点无未访问过的邻接点，则后退寻找，直至全部被访问为止
假如对如下无向图进行深度优先遍历：
假设从A出发[1,0,0,0,0,0,0,0,0]
A有两个邻接点B、D，访问其中一个邻接点B[1,1,0,0,0,0,0,0,0]
B有两个邻接点C、E均未被访问，接下来访问其中一个邻接点C[1,1,1,0,0,0,0,0,0]
C有一个邻接点F均未被访问，接下来访问F[1,1,1,0,0,1,0,0,0]
F的所有邻接点都被访问了，后退到C[1,1,1,0,0,1,0,0,0]
C的所有邻接点都被访问了，后退到B[1,1,1,0,0,1,0,0,0]
B还有一个邻接点E均未被访问，接下来访问E[1,1,1,0,1,1,0,0,0]
E有一个邻接点G均未被访问，接下来访问G[1,1,1,0,1,1,1,0,0]
G有两个邻接点D、H均未被访问，接下来访问D[1,1,1,1,1,1,1,0,0]
D的所有邻接点都被访问了，后退到G[1,1,1,1,1,1,1,0,0]
G还有一个邻接点H未被访问，接下来访问E[1,1,1,1,1,1,1,1,0]
H有一个邻接点I未被访问，接下来访问E[1,1,1,1,1,1,1,1,1]
I的所有邻接点都被访问了，后退到H[1,1,1,1,1,1,1,1,1]
H的所有邻接点都被访问了，后退到G[1,1,1,1,1,1,1,1,1]
G的所有邻接点都被访问了，后退到E[1,1,1,1,1,1,1,1,1]
E的所有邻接点都被访问了，后退到B[1,1,1,1,1,1,1,1,1]
B的所有邻接点都被访问了，后退到A[1,1,1,1,1,1,1,1,1]
现在所有的点均被访问了，深度遍历结束。
则该图的深度优先搜索的输出序列为：
ABCFEGDHI
而广度优先遍历，是指从图的某一顶点V出发，访问顶点；再依次访问V的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。
对一个图进行的广度优先遍历过程如下：
在遍历前，为图设置一个访问标志数组visited[n]，它只有0和1两个值。未遍历的点对应下标的值设为0，已遍历的点对应下标的值设为1。
还是这个无向图，我们现在来进行深度优先遍历：
假设从A出发[1,0,0,0,0,0,0,0,0]
A有三个邻接点B、E、D，访问其中一个邻接点B[1,1,0,0,0,0,0,0,0]
访问第二个邻接点E[1,1,0,0,1,0,0,0,0]
访问第三个邻接点D[1,1,0,1,1,0,0,0,0]
与B、E、D邻接的点有C、G两个未被访问，访问C[1,1,1,1,1,0,0,0,0]
访问G[1,1,1,1,1,0,1,0,0]
与C、G邻接的点有F、H两个未被访问，访问F[1,1,1,1,1,1,1,0,0]
访问H[1,1,1,1,1,1,1,1,0]
与F、H邻接的点有I一个未被访问，访问I[1,1,1,1,1,1,1,1,1]
现在所有的点均被访问了，广度遍历结束。
则该图的广度优先搜索的输出序列为：
ABEDCGFHI
我们来看下面的一个例子
如图所示，在下面的5个序列中，符合深度优先遍历的序列有多少个？
(1)acfdeb(2)aebdfc(3)aedfcb(4)aefdcb(5)aefdbc
A.5个B.4个
C.3个D.2个
现在我们来分析一下这道题
首先我们选一个出发点，由于5个答案中都是以a开始的，我们自然选择a为出发点。从图中可以看出来，与a相连的点有bec三个。
(1)中，a之后是选择c；c只能与f相连；f可以与de相连，这里选择d；与只能与e相连；e与b相连。所以acfdeb是符合深度遍历的结果。
(2)中，a之后是选择e；e可以与bdf相连，这里选择b；与b相连的点都被访问了，所以退回到b，选择下一点d；d只能与f相连；f只能与c相连，所以aebdfc也是符合深度遍历的结果。
(3)中，a之后选择e；e可以与bdf相连。这里选择b；与b相连的点都被访问了，所以退回到b，选择下一点f；f可以与cd相连，这里选择d；与d相连的点都被访问了，退回到f，选择下一点c。所以aedfcb也是符合深度遍历的结果。
(4)中，a之后选择e；e可以与bdf相连，这里选择f；f可以与cd相连，这里选择d；与d相连的都被访问了，退回到f，选择下一点c；与c相连的点都被访问了，退回到f，再退回到e，选择下一点b。所以aefdcb也是符合深度遍历的结果。
(5)中，a之后选择e；e可以与bdf相连，这里选择f；f可以与cd相连，这里选择d；与d相连的都被访问了，退回到f，f只能与c相连，但这里不能选择b。所以aefdbc不是符合深度遍历的结果。
最后答案是B。
友情提醒：数据结构期末考试时间是12月29号，第18周周一。距离考试还有8天
每日一题：
我们来看一道类似的题。
如图所示，在下面的5个序列中，符合深度优先遍历的序列有多少个？
(1)aebdfc(2)acfdeb(3)aedfcb(4)aefdcb(5)aefdbc
为了避免童鞋们不小心看到答案，叫兽把答案放在别处了
点击获取答案吧
哪儿治疗白癜风好头部白癜风和白癜风的区别