软考真题
第161题
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。

【说明】
图是很多领域中的数据模型,遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是:

①访问顶点v;

②访问V的所有未被访问的邻接顶点w1,w2,...,wk;

③依次从这些邻接顶点w1,w2,...,wk出发,访问其所有未被访问的邻接顶点;依此类推,直到图中所有访问过的顶点的邻接顶点都得到访问。

显然,上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u,可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。

例如,对于图4-1所示的有向图G,从a出发进行广度优先遍历,访问顶点的一种顺序为a、b、c、e、f、d。



设图G采用数组表示法(即用邻接矩阵arcs存储),元素arcs[i][j]定义如下:



图4-1的邻接矩阵如图4-2所示,顶点a~f对应的编号依次为0~5。因此,访问顶点a的邻接顶点的顺序为b,c,e。

函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。

相关的符号和类型定义如下:



代码中用到的队列运算的函数原型如表4-1所述,队列类型名为QUEUE。



【问题:4.1】【代码】

第4章数据结构与算法
正确答案:
你的答案:
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2016年 下半年 下午试卷 案例

笔记

请先在App中激活(应用市场搜“软考真题”)

2019-05-23


Gawen

请先在App中激活(应用市场搜“软考真题”)

2024-04-23