目录
三、搜索与图论
3.1 深度优先搜索 \(\sf( DFS)\)和宽度优先搜索\(\sf( BFS)\)
DFS一直往下搜索,直到叶节点才开始回溯,属于一条路走到黑,”不撞南墙不回头“。
BFS每次搜索的时候都搜完这一层的结点,属于“地毯式搜索”,层层推进。
数据结构 | 空间 | 性质(图的边权值均为1时) | |
---|---|---|---|
\(\sf DFS\) | \(\sf stack\) | \(O(h)\)(向下搜的时候只需记录该条路径上的点,空间与高度h成正比) | 不具有最短性 |
\(\sf BFS\) | \(\sf queue\) | \(O(2^h)\)(记录一层的节点数) | 有“最短路”的特性(第一次搜到的是最短路径) |
DFS最重要的是寻找到一个可以遍历完整个搜索树的顺序。
3.2 树和图的存储
树是无环连通图,因此只需考虑图的存储即可。
\[图 \begin{cases} 有向图:对于端点a、b,有有向边a\rightarrow b \\ 无向图:对于端点a、b,建两条有向边 a\rightarrow b,b\rightarrow a即可 \end{cases} \]因此只需考虑有向图的存储:
\[有向图的存储方式: \begin{cases} 邻接矩阵(不能表示重边):g[a][b]\begin{cases} 若无权,则表示a \rightarrow b是否存在\\ 若有权,则表示 a \rightarrow b这条边的权值 \end{cases} 使用较少,适合存储稠密图,空间复杂度为O(n^2) \\ 邻接表 \end{cases} \] 标签:图论,存储,DFS,搜索,cases,sf,rightarrow From: https://www.cnblogs.com/pangyou/p/17853979.html