手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

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

时间:2021/6/2 3:58:24|来源:|点击: 次

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/

Copyright © 2002-2019 某某自媒体运营 版权所有