已知如图1所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为()。 AabcedfBabcefdCaebcfdDacfdeb

已知如图1所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为()。

Aabcedf

Babcefd

Caebcfd

Dacfdeb


参考解析

相关考题:

若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点,则 该图一定是连通图。() 此题为判断题(对,错)。

如果从无向图的某个顶点出发,进行一次广度优先搜索,可访问到图的每个顶点,则该图一定是()图。

已知一个图如图1.1所示,从顶点b出发进行广度优先遍历可能得到的序列为(23)。A.b a c e d fB.b a c d f eC.b a c e f dD.b a c e f d

对图分别进行深度优先遍历和广度优先遍历,得到的顶点访问序列________。 A、一定相同B、一定不同C、不一定相同D、可能相同

若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点,则该图一定是连通图。() 此题为判断题(对,错)。

若从无向图的一个顶点出发进行深度优先遍历可访问到图中所有顶点,则该图一定是连通图。() 此题为判断题(对,错)。

若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点,则该图一定是连通图。() 此题为判断题(对,错)。

已知如图3所示的一个图,若从顶点V1出发,按广度优先法进行遍历,则可能得到的一种顶点序列为( )。A.V1V2V4V8V5V3V6V7B.V1V2V4V5V8V3V6V7C.V1V2V4V8V3V5V6V7D.V1V3V6V7V2V4V5V8

设无向图G中的边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()。A.aedfcbB.acfebdC.aebcfdD.aedfbc

● 对连通图进行遍历前设置所有顶点的访问标志为 false(未被访问) ,遍历图后得到一个遍历序列,初始状态为空。深度优先遍历的含义是:从图中某个未被访问的顶点 v 出发开始遍历,先访问 v 并设置其访问标志为 true(已访问) ,同时将 v 加入遍历序列,再从 v 的未被访问的邻接顶点中选一个顶点,进行深度优先遍历;若 v的所有邻接点都已访问,则回到 v 在遍历序列的直接前驱顶点,再进行深度优先遍历,直至图中所有顶点被访问过。 (40) 是下图的深度优先遍历序列。(40)A. 1 2 3 4 6 5B. 1 2 6 3 4 5C. 1 6 2 5 4 3D. 1 2 3 4 5 6

已知无向图的邻接表如图2-35所示。此邻接表对应的无向图为(1)。此图从F开始的深度优先遍历为(2)。从F开始的广度优先遍历为(3)。从F开始的深度优先生成树为 (4)。从F开始的广度优先生成树为(5)。A.B.C.

阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型,遍历是图的一种基本运算。从图中某顶点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的广度优先遍历。 相关的符号和类型定义如下: define MaxN 50 /*图中最多顶点数*/ typedef int AdjMatrix[MaxN][MaxN]; typedef struct{ int vexnum, edgenum; /*图中实际顶点数和边(弧)数*/ AdjMatrix arcs; /*邻接矩阵*/ )Graph; typedef int QElemType; enum {ERROR=0;OK=1}; 代码中用到的队列运算的函数原型如表4-1所述,队列类型名为QUEUE。 表4-1 实现队列运算的函数原型及说明【代码】 int BFSTraverse(Graph G) {//对图G进行广度优先遍历,图采用邻接矩阵存储 unsigned char*visited; //visited[]用于存储图G中各顶点的访问标志,0表示未访问 int v, w, u; QUEUEQ Q; ∥申请存储顶点访问标志的空间,成功时将所申请空间初始化为0 visited=(char*)calloc(G.vexnum, sizeof(char)); If( (1) ) retum ERROR; (2) ; //初始化Q为空队列 for( v=0; vG.vexnum; v++){ if(!visited[v]){ //从顶点v出发进行广度优先遍历 printf(%d,v); //访问顶点v并将其加入队列 visited[v]=1; (3) ; while(!isEmpty(Q)){ (4) ; //出队列并用u表示出队的元素 for(w=0;vG.vexnum; w++){ if(G.arcs[u][w]!=0 (5) ){ //w是u的邻接顶点且未访问过 printf(%d, w); //访问顶点w visited[w]=1; EnQueue(Q, w); } } } } free(visited); return OK; )//BFSTraverse

具有n个顶点e条边的无向图,若用邻接矩阵作为存储结构,则深度优先或广度优先搜索遍历的时间复杂度为(48);若用邻接表作为存储结构,则深度优先或广度优先搜索遍历时的时间复杂度为(49);深度优先或广度优先搜索遍历的空间复杂度为(50)。A.O(n2)B.O(n)C.O(n-1)D.O(n+1)

试题四(共 15 分)阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】 图是很多领域中的数据模型,遍历是图的一种基本运算。从图中某顶点 v出发进行广度优先遍历的过程是:①访问顶点 v;②访问 V 的所有未被访问的邻接顶点 W1 ,W2 ,..,Wk;③依次从这些邻接顶点 W1 ,W2 ,..,Wk 出发,访问其所有未被访问的邻接顶 点;依此类推,直到图中所有访问过的顶点的邻接顶点都得到访问。显然,上述过程可以访问到从顶点 V 出发且有路径可达的所有顶点。对于 从 v 出发不可达的顶点 u,可从顶点 u 出发再次重复以上过程,直到图中所有顶 点都被访问到。例如,对于图 4-1 所示的有向图 G,从 a 出发进行广度优先遍历,访问顶点 的一种顺序为 a、b、c、e、f、d。图 4-1设图 G 采用数组表示法(即用邻接矩阵 arcs 存储),元素 arcs[i][ j]定义如下: 图 4-1 的邻接矩阵如图 4-2 所示,顶点 a~f 对应的编号依次为 0~5.因此,访问顶点 a 的邻接顶点的顺序为 b,c,e。函数 BFSTraverse(Graph G)利用队列实现图 G 的广度优先遍历。相关的符号和类型定义如下:#define MaxN:50 /*图中最多顶点数*/ typedef int AdjMatrix[MaxN][MaxN];typedef struct{int vexnum,edgenum;/*图中实际顶点数和边(弧)数*/ AdjMatrix arcs; /*邻接矩阵*/)Graph;typedef int QElemType; enum {ERROR=0;OK=l};代码中用到的队列运算的函数原型如表 4-1 所述,队列类型名为 QUEUE。表 4-1 实现队列运算的函数原型及说明 【代码】int BFSTraverse(Graph G){//图 G 进行广度优先遍历,图采用邻接矩阵存储unsigned char*visited; //visited[]用于存储图 G 中各顶点的访问标 志,0 表示未访问int v,w;u; QUEUEQ Q;∥申请存储顶点访问标志的空间,成功时将所申请空间初始化为 0 visited=(char*)calloc(G.vexnum, sizeof(char));If( (1) ) retum ERROR; (2) ; //初始化 Q 为空队列 for( v=0; v } free(visited);return OK;)//BFSTraverse从下列的 2 道试题(试题五至试题六)中任选 1 道解答。请在答题纸上的 指定位置处将所选择试题的题号框涂黑。若多涂或者未涂题号框,则对题号最小 的一道试题进行评分。

下面关于图的遍历说法不正确的是()。A.遍历图的过程实质上是对每个顶点查找其邻接点的过程B.深度优先搜索和广度优先搜索对无向图和有向图都适用C.深度优先搜索和广度优先搜索对顶点访问的顺序不同,它们的时间复杂度也不相同D.深度优先搜索是一个递归的过程,广度优先搜索的过程中需附设队列

如图若从顶点a出发按深度优先搜索法进行遍历,则可能得到的顶点序列为()。 AacfgedbBaedbgfcCacfebdgDaecbdgf

已知如图所示的一个图,若从顶点a出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。 AabecdfBacfebdCaedfcbDaebcfd

已知如图所示的一个图,若从顶点V1出发,按广度优先法进行遍历,则可能得到的一种顶点序列为()。 AV1V2V4V8V5V3V6V7BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7DV1V3V6V7V2V4V5V8

如图若从顶点a出发按广度优先搜索法进行遍历,则可能得到的顶点序列为()。 AacebdfghBaebcghdfCaedfbcghDabecdfgh

若从无向图中任意一个顶点出发进行1次深度优先搜索便可以访问到该图的所有顶点,则该图一定是一个()。A、非连通图B、强连通图C、连通图D、完全图

设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为()A、abedfcB、acfebdC、aebdfcD、aedfcb

对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。

对于任意一个图,从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点

单选题设连通图G中的边集E={(a,b),(a,e),(a,c),(a,e),(b,d),(d,f),(f,c)),则从顶点a出发可以得到一种深度优先遍历的顶点序列为()。AabedfcBacfebdCabcedfDabcdef

判断题对有向图G,如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点,则该图一定是完全图。A对B错

单选题若一个图的边集为{,,,,,},则从顶点1开始对该图进行广度优先搜索,得到的顶点序列可能为()。A 1,2,3,4,5B 1,2,4,3,5C 1,2,4,5,3D 1,4,2,5,3

判断题对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。A对B错