深度优先搜索
标签: 数据结构
学习人数: 19.5k

深度优先遍历(Depth First Search)的主要思想是:

1、首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点;

2、当没有未访问过的顶点时,则回到上一个顶点,继续试探别的顶点,直至所有的顶点都被访问过。

在此我想用一句话来形容 “不撞南墙不回头”。

 

无向图的深度优先遍历图解
以下"无向图"为例:

对上无向图进行深度优先遍历,从A开始:

第1步:访问A。

第2步:访问B(A的邻接点)。 在第1步访问A之后,接下来应该访问的是A的邻接点,即"B,D,F"中的一个。但在本文的实现中,顶点ABCDEFGH是按照顺序存储,B在"D和F"的前面,因此,先访问B。

第3步:访问G(B的邻接点)。 和B相连只有"G"(A已经访问过了)  

第4步:访问E(G的邻接点)。 在第3步访问了B的邻接点G之后,接下来应该访问G的邻接点,即"E和H"中一个(B已经被访问过,就不算在内)。而由于E在H之前,先访问E。

第5步:访问C(E的邻接点)。 和E相连只有"C"(G已经访问过了)。

第6步:访问D(C的邻接点)。 

第7步:访问H。因为D没有未被访问的邻接点;因此,一直回溯到访问G的另一个邻接点H。

第8步:访问(H的邻接点)F。

因此访问顺序是:A -> B -> G -> E -> C -> D -> H -> F

 

有向图的深度优先遍历
有向图的深度优先遍历图解:

对上有向图进行深度优先遍历,从A开始:

第1步:访问A。

第2步:访问(A的出度对应的字母)B。 在第1步访问A之后,接下来应该访问的是A的出度对应字母,即"B,C,F"中的一个。但在本文的实现中,顶点ABCDEFGH是按照顺序存储,B在"C和F"的前面,因此,先访问B。

第3步:访问(B的出度对应的字母)F。 B的出度对应字母只有F。 

第4步:访问H(F的出度对应的字母)。 F的出度对应字母只有H。 

第5步:访问(H的出度对应的字母)G。

第6步:访问(G的出度对应字母)E。 在第5步访问G之后,接下来应该访问的是G的出度对应字母,即"B,C,E"中的一个。但在本文的实现中,顶点B已经访问了,由于C在E前面,所以先访问C。

第7步:访问(C的出度对应的字母)D。

第8步:访问(C的出度对应字母)D。 在第7步访问C之后,接下来应该访问的是C的出度对应字母,即"B,D"中的一个。但在本文的实现中,顶点B已经访问了,所以访问D。

第9步:访问E。D无出度,所以一直回溯到G对应的另一个出度E。

因此访问顺序是:A -> B -> F -> H -> G -> C -> D -> E

 

代码实现

可参考《计算机考研机试攻略》部分:http://www.noobdream.com/Major/article/133/

登录查看完整内容


课后作业

课后习题

 

【2016年真题】下列选项中,不是下图深度优先搜索序列的是()

A.V1,V5,V4,V3,V2        B.V1,V3,V2,V5,V4
C.V1,V2,V5,V4,V3        D.V1,V2,V3,V4,V5

参考答案:D

 

【2015年真题】设有向图 G=(V,E),顶点集 V={V0,V1,V2,V3},边集 E={<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>}。若从顶点 V0 开始对图进行深度优先遍历,则可能得到的不同遍历序列个数是()。
A.2    B.3    C.4    D.5

参考答案:D


登录后开始许愿

暂无评论,来抢沙发