2. 计算机
  3. 如图所示，在下面的5个序列中符合深度优先遍历的序列有(45)个。　　　　 aebdfc，acfdeb，aedfcb，aefdcb，aefdbc

如图所示，在下面的5个序列中符合深度优先遍历的序列有(45)个。　　　　 aebdfc，acfdeb，aedfcb，aefdcb，aefdbc

admin2009-02-15  45
问题 如图所示，在下面的5个序列中符合深度优先遍历的序列有(45)个。　　　　
aebdfc，acfdeb，aedfcb，aefdcb，aefdbc
选项 A、2个
B、3个
C、4个
D、5个
答案C
解析 图的深度优先搜索遍历过程是：首先E一个出发顶点v，并访问之，接着选择一个与v相邻接并且未被访问过的顶点w访问之，再从w开始进行深度优先搜索遍历。每当到达一个其所有相邻接的顶点都已被访问过的顶点时，就从最近所访问的顶点开始依次回退，直至退回某个顶点，该顶点尚有未曾访问过的邻接顶点，再从该邻接顶点开始继续进行深度优先搜索遍历。上述过程在两种可能情况下终止；所有顶点已都被访问，或从任一个已被访问过的顶点出发，再也无法到达未曾访问过的顶点。　对于无向图，如果图是连通的，那么按深度优先搜索遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。从a出发，aebdfc、acfdeb、aedfcb、aefdcb都是符合深度优先遍历的序列。但aefdbc不是，因为走过aefd之后，与d相邻接的顶点都已被访问过，所以从最近访问的顶点开始依次回退，当回退到f时与f相邻接的结点只有c未被访问过就访问c，然后又回退至e再访问b，因此只能是aefdcb，而不能是aefdbc，所以应选4个。
转载请注明原文地址:https://kaotiyun.com/show/4QjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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