对如图所示的有向图G，请给出其广度优先遍历序列，并画其DFS子树(以A为源点)。

admin2010-04-24 64

问题对如图所示的有向图G，请给出其广度优先遍历序列，并画其DFS子树(以A为源点)。

选项

答案图的广度优先遍历类似于树的按层遍历：首先访问源点，并将其记为访问过，接着访问vi的所有未被访问的邻接点vi1，vi2，…，vit。并将它们均记为已经访问过，然后再按照vi1，vi2，…，vit的次序，访问每个顶点的所有未被访问的邻接点，并均记它们为已访问过，按此规则类推，直到图中所有和源点vi有路径相通的顶点都访问过为止。则按照广度优先遍历规则，我们得到此遍历序列为ABCDEFGHI。相应的子树为： [*]

解析

转载请注明原文地址:https://kaotiyun.com/show/qMAx777K

本试题收录于：数据结构题库理工类分类