题目

无向图 G＝（V，E），其中:V＝(a，b，c，d，e，f)，E＝(（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）)，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A. a，b，e，c，d，fB. a，c，f，e，b，dC. a，e，b，c，f，dD. a，e，d，f，c，b

无向图 G＝（V，E），其中:V＝{a，b，c，d，e，f}，E＝{（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A. a，b，e，c，d，f
B. a，c，f，e，b，d
C. a，e，b，c，f，d
D. a，e，d，f，c，b

题目解答

答案

【答案】D【解析】图的深度优先遍历过程是：从图中某个初始顸点 v 出发，首先访问初始顶点 v，然后选择一个与顶点 v 相邻且没被访问过的顶点 u 为初始顶点。再从 u 出发进行深度优先搜索，直到图中与当前顶点 v 邻接的所有顶点都被访问过为止。根据 E ＝ { （ a ， b ），（ a ， e ），（ a ， c ），（ b ， e ），（c，f），（f，d），（e，d）}可知各顶点之间的邻接关系。依据上面的原则遍历，得出遍历顺序 a，e，d，f，c，b。

解析

步骤 1：确定初始顶点
从顶点 a 开始进行深度优先遍历。
步骤 2：访问与 a 相邻的顶点
与 a 相邻的顶点有 b、e、c。选择 e 作为下一个访问的顶点。
步骤 3：访问与 e 相邻的顶点
与 e 相邻的顶点有 b、d。选择 d 作为下一个访问的顶点。
步骤 4：访问与 d 相邻的顶点
与 d 相邻的顶点有 f。选择 f 作为下一个访问的顶点。
步骤 5：访问与 f 相邻的顶点
与 f 相邻的顶点有 c。选择 c 作为下一个访问的顶点。
步骤 6：访问与 c 相邻的顶点
与 c 相邻的顶点有 a、f。a 已经被访问过，所以选择 b 作为下一个访问的顶点。
步骤 7：访问与 b 相邻的顶点
与 b 相邻的顶点有 a、e。a 和 e 已经被访问过，所以遍历结束。