本章节为Acwing基础算法系列中的搜索与图论部分，涵盖深度优先搜索、广度优先搜索及各类图的存储和遍历等核心内容。
这次字写的有点小了，需要放大才能看清，请注意后面笔记会写大一点的。图论这部分的知识是根据y总的思路编写的代码，逻辑清晰、易于理解。不过还需要多加练习以巩固记忆，因为不练就会忘。
【Acwing-基础算法-第三章-搜索与图论】主要介绍了两个核心概念：搜索算法和图论，并重点讲解了如何用搜索算法解决图论问题。
1. **深度优先搜索（DFS, Depth-First Search）**
- DFS是一种用于遍历或搜索树或图形的策略。在图形中，它沿着某条路径尽可能深入地进行探索，直到达到叶节点，然后回溯。
- 在图形的DFS遍历过程中，每个顶点会被访问一次且仅被访问一次。这种算法常用于寻找图中的环、判断连通性以及找到两个顶点之间的最短路径等。
- 实现中通常使用栈来辅助操作：每次访问一个节点并标记为已访问状态，并递归地对相邻的未访问节点进行搜索。
2. **宽度优先搜索（BFS, Breadth-First Search）**
- BFS从根顶点开始，一层层地探索树或图形。在树中，BFS通常使用队列来进行操作。
- 它能够有效地找到两个顶点之间的最短路径（当所有边的权重相等时）。在图的BFS遍历过程中，每个节点被访问一次且仅被访问一次。
- 实现中通常用队列来辅助：先处理距离起点近的节点，再处理远一点的节点。
3. **拓扑排序**
- 拓扑排序是对有向无环图（DAG, Directed Acyclic Graph）的一种线性排列方式。它将所有顶点排成一个序列，使得对于任何边 (u, v)，顶点 u 总是出现在顶点 v 之前。
- 可以通过BFS或DFS来实现拓扑排序，确保没有边指向已经排序的节点。
4. **图的存储方式**
- **邻接矩阵**：使用二维数组表示每个元素是否代表两个顶点之间存在连接。适用于稠密图形（边数接近于顶点数量平方）。
- **邻接表**：对于稀疏图形，即边的数量远小于节点数量的情况，则采用链表存储方式更为节省空间。
5. **树与图的遍历**
- 树的遍历可以视为有向无环图（DAG）中的一种特殊情形。包括前序、中序和后序三种类型的遍历，分别对应于DFS的不同顺序。
- 在树结构中的前序遍历为根-左子树-右子树；中序遍历为左子树-根节点-右子树；而后序遍历则是先处理左右子树再访问根。
6. **八皇后问题**
- 八皇后问题是图论领域的一个经典示例，目标是在8x8的棋盘上放置八个皇后，确保任意两个皇后的摆放不会在同一行、同一列或同一条对角线上。
- 解决这个问题通常采用DFS方法：将每一种可能的状态视为一个节点，并通过移动皇后来探索相邻状态间的路径。
7. **最短路径算法**
- 对于无权图的最短路径问题，BFS能够找到两顶点之间的最短距离（前提是所有边权重相同）。
- 而在有向加权图形中，则可以使用Dijkstra或A*算法来寻找单源最短路径。其中，A*算法通过引入启发式函数提高了搜索效率。
以上就是对图论和搜索领域基础知识的简要介绍。实际应用时需要结合各种复杂的问题进行深入学习和实践练习才能完全掌握这些概念和技术。记住，不断的应用与练习是巩固知识的关键。
5星
