目 录CONTENT

文章目录

【数据结构】--图的遍历BFS和DFS算法

geekrabbit
2022-10-07 / 0 评论 / 0 点赞 / 736 阅读 / 674 字 / 正在检测是否收录...
温馨提示:
创作不易,转载请注明出处

BFS-广度优先算法

类似于二叉树的层遍历算法

BFS算法的性能分析

时间复杂度

首先,我们需要确定BFS遍历的时间开销来源是什么,这是最重要的,BFS遍历的时间开销有二:访问节点+探索边。访问节点需要遍历整个图,因此时间复杂度为O(V),而遍历边,需要在二维数组中查看每一个节点与其相连的边。因此对于邻接矩阵存储模式,总的时间开销为O(V+V2),保留最大项,为O(V2),而对于邻接矩阵存储,遍历节点的时间复杂度为O(V),遍历边则直接遍历边节点即可,因此遍历边的时间复杂度为O(E),故总的时间复杂度为O(V+E)

空间复杂度

使用了辅助队列,n个节点均需要入队一次,故空间复杂度为O(V)

DFS-深度优先遍历

深度优先算法类似于树的先序遍历,和递归差不多,就是一条路走到黑,走不通在返回去,直到找到能通的路线

DFS算法的性能分析

时间复杂度

以邻接表表示时,查找所有顶点的邻接点所需的时间为O(E),访问顶点所需的时间为O(V),此时,总的时间复杂度为O(V+E)。

以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为0(V),故总的时间复杂度为

空间复杂度

DFS算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为O(V)。

BFS-广度优先算法和DFS-深度优先算法遍历过程

BFS-广度优先算法和DFS-深度优先算法生成树的画法

0
博主关闭了所有页面的评论