对于下图，从顶点1进行深度优先遍历时，不可能得到遍历序列是( )；若将该图用邻接矩阵存储，则矩阵中非0元素数目为(请作答此空)。
- A.7
- B.8
- C.14
- D.16
正确答案及解析
正确答案
B
解析
本题考查数据结构基础知识。
对题中所示图从顶点1出发进行深度优先遍历，访问l之后接下来既可以访问顶点2，也可以访问顶点5。
若先访问顶点2，则接下来可以访问顶点3或6，此时得到已访问顶点顺序是123或126。若选择先访问顶点3，则接下来就访问顶点4，便得到已访问顶点顺序1234，由于从顶点4出发不存在继续前进路径，所以需要先回溯至顶点3再回溯至顶点2。由于顶点2存在尚没有得到访问邻接顶点6，所以接下来访问顶点是6，然后是顶点7，从而得到己访问顶点遍历序列123467。最后还需回溯至顶点1，再去访问顶点5，这样就完成了所有顶点访问，从而得到深度优先遍历序列1234675。若访问完顶点2后接下来选择访问顶点6，则可得到遍历序列1263475或1267435。
若访问完顶点1之后接下来选择访问顶点5，则可得到深度优先遍历序列1523467或1526347或1526734。
因此，不能得到深度优先遍历序列是1234567。
对于有向图，其邻接矩阵中非零元素个数即表示图中有向弧数目，题中图有8条弧，因此矩阵中非0元素数目为8，如下图所示。
