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

广度优先遍历(Breadth First Search)的主要思想是:类似于树的层序遍历。

 

无向图的广度优先遍历图解:

从A开始,有4个邻接点,“B,C,D,F”,这是第二层;

在分别从B,C,D,F开始找他们的邻接点,为第三层。以此类推。

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

 

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

与无向图类似 。可以参考。

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

 

代码实现

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

登录查看完整内容


课后作业

课后习题

 

【2013年真题】若对如下无向图进行遍历,则下列选项中,不.是广度优先遍历序列的是()

A. h,c,a,b,d,e,g,f        B. e,a,f,g,b,h,c,d 
C. d,b,c,a,h,e,f,g         D. a,b,c,d,h,e,f,g

参考答案:D
答案解析:D 选项是深度优先遍历不是广度优先遍历的顺序。 

 

【2012年真题】对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是()。
A.O(n) 
B.O(e) 
C.O(n+e) 
D.O(n*e) 

参考答案:C
答案解析:考查不同存储结构的图遍历算法的时间复杂度。 
广度优先遍历需要借助队列实现。邻接表的结构包括:顶点表;边表(有向图为出边表)。当采用邻接表存储方式时,在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历),故时间复杂度为O(n),在搜索所有顶点的邻接点的过程中,每条边至少访问一次(出边表遍历),故时间复杂度为 O(e),算法总的时间复杂度为 O(n+e)。 


登录后开始许愿

暂无评论,来抢沙发