数据结构深度优先遍历:

设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为( )。
(A)abedfc (B) acfebd (C) aebdfc (D) aedfcb

图的深度优先遍历类似于树的前序遍历。首先访问出发点a,并将其标记为已访问过;然后依次从a出发搜索a的每个邻接点b,c,e。若b未曾访问过,则以b为新的出发点继续进行深度优先遍历,直至图中所有和源点a有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
所以从a出发,找a的下一个点,a下一个点有b、c、e,首先到b,再以b为源点,再看b有没有下一个点,发现b的下一个点是e,再以e为源点,e的下一个点是d,再以d为源点,下一个点是f,再以f的下一个点是c。
这样全部的点都得到了,该序列就是该图的深序优先遍历。即abedfc,选A。
这里刚好一次就全部遍历了,要是没有下一个点的话,还要回到上一个点,继续查找其它点。以此类推。
希望我的回答对您有帮助~如果有不清楚的可以继续问我。

参考资料:by 5220

温馨提示:答案为网友推荐,仅供参考
第1个回答  2012-11-29
A
相似回答