试题详情
简答题已知一个无向图的邻接表如图所示，要求： 根据邻接表，分别写出用DFS（深度优先搜索）和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。
  • 根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。
    从图的逻辑结构上来讲，从图中某个顶点开始的深度（或广度）优先遍历序列不一定是唯一的。这是因为在逻辑结构中，并没有对每个顶点的所有邻接点规定它们之间的先后顺序，这样在搜索算法中选取第—个邻接点和下一个邻接点时可能会有不同的结果。但是在存储结构中，明确地给出了邻接点的先后顺序，这时深度优先和广度优先遍历序列就是唯一的。

  • 关注下方微信公众号，在线模考后查看

热门试题