2. 从业资格
  3. 针对下图所示的有向图，从结点V1出发广度遍历所得结点序列和深度遍历所得结点序列分

针对下图所示的有向图，从结点V1出发广度遍历所得结点序列和深度遍历所得结点序列分

题库2022-08-02  89
问题 针对下图所示的有向图，从结点V1出发广度遍历所得结点序列和深度遍历所得结点序列分别是______。A.V1，V2，V3，V4，V5，V6，V7，V8和V1，V2，V3，V8，V5，V7，V4，V6B.V1，V2，V4，V6，V3，V5，V7，V8和V1，V2，V3，V8，V5，V7，V4，V6C.V1，V2，V4，V6，V3，V5，V7，V8和V1，V2，V3，V8，V4，V5，V6，V7D.V1，V2，V4，V6，V7，V3，V5，V8和V1，V2，V3，V8，V5，V7，V4，V6
选项 A.V1，V2，V3，V4，V5，V6，V7，V8和V1，V2，V3，V8，V5，V7，V4，V6
B.V1，V2，V4，V6，V3，V5，V7，V8和V1，V2，V3，V8，V5，V7，V4，V6
C.V1，V2，V4，V6，V3，V5，V7，V8和V1，V2，V3，V8，V4，V5，V6，V7
D.V1，V2，V4，V6，V7，V3，V5，V8和V1，V2，V3，V8，V5，V7，V4，V6
答案 B
解析 本题考查遍历方面的基础知识。图的广度优先遍历是先访问顶点V1，然后访问V1邻接到的所有未被访问过的顶点V2，V3，…，Vt邻接到的所有未被访问的顶点。如此进行下去，直到访问遍所有顶点，因此，本题中图的广度优先遍历是V1，V2，V4，V6，V3，V5，V7，V8。深度优先遍历是从图中某个结点，例如V1出发，访问此结点，然后依次从V1的未被访问的邻接顶点出发进行深度优先遍历，直至图中所有和V1有路径想通的结点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未被访问过的顶点作起始顶点，重复上述过程，直至图中所有顶点都被访问到为止。因此，本题中图的深度优先遍历是V1，V2，V3，V8，V5，V7，V4，V6。
转载请注明原文地址:https://tihaiku.com/congyezige/2424742.html
本试题收录于： 中级 嵌入式系统设计师题库软件水平考试初中高级分类

中级 嵌入式系统设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)