如果从无向图的任一顶点出发进行一次DFS遍历即可访问所有顶点,则该图一定是A.完全图B.连通图C.有回路D.一棵树

如果从无向图的任一顶点出发进行一次DFS遍历即可访问所有顶点,则该图一定是

A.完全图

B.连通图

C.有回路

D.一棵树


参考答案和解析
连通图

相关考题:

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

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

● 若无向连通图 G 具有 n个顶点,则以下关于图 G的叙述中,错误的是(43)。(43)A.G 的边数一定多于顶点数B.G 的生成树中一定包含 n个顶点C.从 G 中任意顶点出发一定能遍历图中所有顶点D.G 的邻接矩阵一定是n阶对称矩阵

下列说法正确的是【】A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.遍历的基本算法有两种:深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程

图的遍历要求从图的某一顶点出发,访遍图中的其余顶点,且每个顶点仅被访问一次。() 此题为判断题(对,错)。

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

图的遍历是从图中的某个顶点出发,按照某种搜索策略访问图中所有顶点且每个顶点仅访问一次。() 此题为判断题(对,错)。

如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。 A.一棵树B.有回路C.完全图D.连通图

阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。1. 【说明】实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。【算法】第一步:首先访问连通图G的指定起始顶点v;第二步:从V出发,访问一个与v(1)p,再从顶点P出发,访问与p(2)顶点q,然后从q出发,重复上述过程,直到找不到存在(3)的邻接顶点为止。第三步:回退到尚有(4)顶点,从该顶点出发,重复第二、三步,直到所有被访问过的顶点的邻接点都已被访问为止。因此,在这个算法中应设一个栈保存被(5)的顶点,以便回溯查找被访问过顶点的未被访问过的邻接点。

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

● 对连通图进行遍历前设置所有顶点的访问标志为 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

以下关于图的遍历的叙述中,正确的是(61)。A.图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程B.图的深度优先遍历方法不适用于无向图C.使用队列对图进行广度优先遍历D.图中有回路时则无法进行遍历

阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型,遍历是图的一种基本运算。从图中某顶点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

试题四(共 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 道解答。请在答题纸上的 指定位置处将所选择试题的题号框涂黑。若多涂或者未涂题号框,则对题号最小 的一道试题进行评分。

调用一次深度优先遍历可以访问到图中的所有顶点。()

阅读下列说明和?C?代码,回答问题?1?至问题?2,将解答写在答题纸的对应栏内。【说明】一个无向连通图?G?点上的哈密尔顿(Hamiltion)回路是指从图?G?上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下:假设图?G?存在一个从顶点?V0?出发的哈密尔顿回路?V1——V2——V3——...——Vn-1——V0。算法从顶点?V0?出发,访问该顶点的一个未被访问的邻接顶点?V1,接着从顶点?V1?出发,访问?V1?一个未被访问的邻接顶点?V2,..。;对顶点?Vi,重复进行以下操作:访问?Vi?的一个未被访问的邻接接点?Vi+1;若?Vi?的所有邻接顶点均已被访问,则返回到顶点?Vi-1,考虑Vi-1?的下一个未被访问的邻接顶点,仍记为?Vi;知道找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。【C?代码】下面是算法的?C?语言实现。(1)常量和变量说明n :图?G?中的顶点数c[][]:图?G?的邻接矩阵K:统计变量,当期已经访问的定点数为?k+1x[k]:第?k?个访问的顶点编号,从?0?开始Visited[x[k]]:第?k?个顶点的访问标志,0?表示未访问,1?表示已访问⑵C?程序【问题?1】(10?分)根据题干说明。填充?C?代码中的空(1)~(5)。【问题?2】(5?分)根据题干说明和?C?代码,算法采用的设计策略为( ),该方法在遍历图的顶点时,采用的是(?)方法(深度优先或广度优先)。

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

如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。A、完全图B、连通图C、有回路D、一棵树

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

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

如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。

单选题用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是( )。A逆拓扑有序B拓扑有序C无序的D无法判断

填空题如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。

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

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

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

单选题如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。A一棵树B有回路C完全图D连通图

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