2. 考研
  3. 己知一个有向图的邻接表存储结构如右图所示，根据有向图的深度优先遍历算法，从顶点l出发，所得到的顶点序列是( )。

己知一个有向图的邻接表存储结构如右图所示，根据有向图的深度优先遍历算法，从顶点l出发，所得到的顶点序列是( )。

admin2019-12-10  45
问题 己知一个有向图的邻接表存储结构如右图所示，根据有向图的深度优先遍历算法，从顶点l出发，所得到的顶点序列是(    )。
选项 A、1，2，3，5，4
B、1，2，3，4，5
C、1，3，4，5，2
D、1，4，3，5，2
答案C
解析 考查深度优先遍历。深度优先遍历是找到新的访问结点后，就从新结点开始找新的访问结点，如果没有找到，回溯到上一个找到的新的访问结点继续查找。从顶点1出发，下一个新访问结点3，从3开始，找到4，从4开始，没有新结点，回溯到3，找到新访问结点5，从5开始，找到2，从2开始没有新结点，回溯到5，没有新结点，回溯到3，没有新节结，回溯到1，没有新结点，访问结束。所以得到的顶点序列为1，3，4，5，2。
    注：当一个图只给了相应的图形时，那么它采用哪一种遍历方式，遍历序列一般都是不唯一的，但是在给定了存储结构(邻接矩阵或邻接表等)时，一般相应的遍历序列都是唯一的。
转载请注明原文地址:https://jikaoti.com/ti/4eDjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)