单项选择(2014年秋程序员软考)

对于下图,从顶点1进行深度优先遍历时,不可能得到的遍历序列是【 】

A、1234567

B、1523467

C、1234675

D、1267435

答案解析

A对题中所示的图从顶点1出发进行深度优先遍历,访问1之后接下来既可以访问顶点2,也可以访问顶点5。若先访问顶点2,则接下来可以访问顶点3或6,此时得到的已访问顶点顺序是123或26。若选择先访问顶点3,则接下来就访问顶点4,便得到已访问的顶点顺序1234,由于从顶点4出发不存在继续前进的路径,所以需要先回溯至顶点3再回溯至顶点2。由于顶点2存在尚没有得到访问的邻接顶点6,所以接下来访间的顶点是6,然后...

查看完整答案

讨论