针对下图所示的有向图，从结点V1出发广度遍历所得结点序列和深度遍历所得结点序列分别是（ ）。(2014年嵌入式系统设计师)

针对下图所示的有向图，从结点V1出发广度遍历所得结点序列和深度遍历所得结点序列分别是（   ）。(2014年嵌入式系统设计师)

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。