题目
无向图 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. 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 已经被访问过,所以遍历结束。
从顶点 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 已经被访问过,所以遍历结束。