当前位置: article > 正文

深度优先遍历算法

作者：很楠不爱3 | 2024-04-29 14:03:35

踩

深度优先遍历算法

1 基本思想

深度优先遍历算法类似于二叉树的先序遍历算法。

首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任意一个顶点w1,再访问与w1邻接且未被访问的任意一个顶点w2……重复上述过程，当不能在继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

2 实例

首先访问a，并置a访问标记；然后访问与a邻接且未被访问的顶点b，置b访问标记；然后访问与b邻接且未被访问的顶点d，置d访问标记。此时d已没有未被访问过的邻接点，故返回上一个访问过的顶点b，访问与其邻接且未被访问的顶点e，置e访问标记……依次类推，直至图中所有的顶点都被访问一次。遍历结果为abdehcfg。

3 深度优先遍历算法的性能分析

(1)空间复杂度：O(|V|)

(2)时间复杂度

采用邻接矩阵存储方式： $O(|V|^{2})$
采用邻接表存储方式： $O(|V|+|E|)$

4 深度优先生成树

与广度优先遍历算法类似，基于邻接表存储的深度优先生成树是不唯一的。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/508140