广度优先搜索&深度优先搜索(Breadth First Search & Depth First Search) BFS优缺点: 同一层的所有节点都会加入队列,所以耗用大量空间 仅能非递归实现 相比DFS较快,空间换时间 适合广度大的图 空间复杂度:邻接矩阵O(N^2);邻接表O(N+E) 时间复杂度:O(V+E) DFS优缺点: 无论是系统栈还是用户栈保存的节点数都只是树的深度,所以空间耗用小 有递归和非递归实现 由于有大量栈操作(特别是递归实现时候的系统调用),执行速度较BFS慢 适合深度大的图 空间复杂度:邻接矩阵O(N^2);邻接表O(N+E) 时间复杂度:O(V+E) //BFS只能非递归实现,将queue替换成stack之后就是DFS
Comments
Post a Comment