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

Question

针对下图所示的有向图，从结点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

Answer 1

正确答案：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.