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

02
六月
2021

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/

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员