算法的比较
广度优先搜索&深度优先搜索（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