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

admin2009-02-15  18

问题 如图所示,在下面的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)