Question

以下关于图的遍历的叙述中，正确的是（　　）。

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

Answer 1

【答案】：C
图的遍历是指，从某一个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且仅访问一次的过程，所以回路不影响遍历，D选项错误。
这里的访问是沿着某条搜索路径，并不是任意的。A选项错误。
图的深度优先可以用于有向图，也可以用于无向图，B选项错误。
广度优先遍历的特点是尽可能横向搜索，即最先访问的顶点的邻接顶点也先被访问。为此，引入队列来保存，能够先进先出，即当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接顶点并让这些顶点入队。队列的特点是先进先出，广度优先刚好合适，C选项正确。