三、搜索与图论
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}
\]