您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

AcWing 算法基础课笔记 3.搜索与图论(持续更新)

AcWing 算法基础课笔记 3.搜索与图论

  • 深度优先遍历DFS与宽度优先遍历BFS
    • 二者对比
    • DFS


深度优先遍历DFS与宽度优先遍历BFS

二者对比

都可以对整个搜索空间进行遍历。
搜索的时候都是像一棵树一样搜索。

但是搜索的顺序不一样:
DFS 优先深度,到不能再前进的时候(叶子节点)再回溯。
BFS 一层层搜索,搜索完每一代节点后,再搜索下一代节点。

DFSBFS
数据结构stackqueue
空间O(h)O(2h)

DFS 在空间使用上有优势,但不具有最短路性。
BFS 有一个最短路的概念,即假设树中每条边的权重均为1, BFS 搜索到某一个点的路径,一定是最短距离。

最小步数、最短距离,最少操作等:BFS
算法思路较奇怪或者空间要求较高:DFS

DFS

最重要的考虑点在于:顺序。决定要以什么样的顺序来进行。


有些较复杂的懒得写特别细,建议AcWing学一下y总的课效果更好。
以上截图和模板均来源:AcWing
链接:https://www.acwing.com/blog/content/404/


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进