邻接表按深度优先遍历和按广度优先遍历的序列

• 算法结构

求此邻接表的深度优先遍历序列和广度优先遍历序列。

邻接表按深度优先遍历和按广度优先遍历的序列

  深度优先：按深度优先遍历时会有类似”跳转”的操作，比如例1中顶点v1→边v2后，会直接跳转到顶点v2去，再重新从顶点v2→边v1，由于v1访问过，所以变为v2→边v5，再跳转到顶点v5去，直到每个顶点都被访问过。抽象理解为”跳转”，实际上是递归。那么例1按深度优先遍历的序列如下：

v1→v2→v5→v3→v4→v6

  广度优先：按广度优先遍历实际上就是一条路走到黑， 比如例1中顶点v1→边v2→边v3→边v4，此时，再从顶点v2开始，顶点v2→边v1(访问过)→边v5，再从顶点v3开始，再从顶点v4开始……直到每个顶点都被访问过。实际上里面运用了队列，这个和二叉树按层次遍历非常相似。那么例1按广度优先遍历的序列如下：

v1→v1→v3→v4→v5→v6

 

留下一题试试身手，答案在评论区。

邻接表按深度优先遍历和按广度优先遍历的序列

 

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/ffded2771c.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐