问题详情

针对下图所示的有向图,从结点V1出发广度遍历所得结点序列和深度遍历所得结点序列分别是()。


A、V1,V2, V3&39; V4. V5, V6. V7&39; V8和Vl, V2, V3. V8. V5, V7. V4. V6

B、V1, V2,V4,V6,V3,V5,V7,V8和Vl, V2, V3. V8. V5,V7. V4. V6

C、V1, V2,V4,V6,V3,V5,V7,V8和Vl, V2, V3. V8.V4V5,V6,V7

D、V1, V2,V4,V6,V7. V3,V5,V8和Vl, V2, V3. V8. V5,V7. V4. V6

时间:2022-01-04 04:01 关键词:

答案解析

B
本题考查遍历方面的基础知识。图的广度优先遍历是先访问顶点vl,然后访问vl邻接到的所有未被访问过的顶点V2,V3…,vt邻接到的所有未被访问的顶点。如此进行下去,直到访问遍所有顶点,因此,本题中图的广度优先遍历是vl,V2,V4,V6,V3,V5.V7,V8。深度优先遍历是从图中某个结点,例如vl出发,访问此结点,然后依次从vl的未被访问的邻接顶点出发进行深度优先遍历,直至图中所有和vl有路径想通的结点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未被访问过的顶点作起始顶点,重复上述过程,直至图中所有顶点都被访问到为止。因此,本题中囤的深度优先遍历是Vl.V2.V3,V8.V5,V7.V4.V6.