DFS与BFS
DFS模板
1 | void dfs(int x) { |
八数码
该题的一个关键是状态表示,如何判断9个数字都归位了,这里用的方法是将它们压缩到一个string中,通过判断string是否相等来确认是否归位。通过哈希表来保存每个状态的最少交换次数,string是一维的,而实际上其中的数字具有二维的空间关系,使用除和余来提取这种关系。
1 |
|
图上DFS和BFS
树的重心
1 |
|
图中点的层次
1 |
|
拓扑排序
拓扑序列一定是有向无环图,因此一定存在入度为0的点,如果从所有入度为0的点开始进入BFS访问,将访问过程中遇到的入度为0的点加入队列,则若存在拓扑序列应能遍历所有顶点,且入队的顺序就是一个拓扑排序。
1 |
|
Dijkstra
Dijkstra用于计算一个节点到其他节点的最短路径。(单源最短路)
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。且在扩展过程中,贪心的选择这些点。
该算法要求图中『 不存在负权边 』。
- 算法思想
两个集合S、U。S中为已确定最短路径的顶点,U中为未确定的,算法开始先将起点加入S,更新新加入的点对U中顶点到S的最短距离。然后不断循环从U中寻找到S最近的顶点,加入S、更新距离。直到全部加入S。
1 |
|
在朴素版本的dijkstra中,查找未加入的点中距离最短的点的复杂度是O(n) 的,当顶点数很多时,容易超时,因此可以用堆来优化最短距离的查找。
1 |
|
公交路线
1 | class Solution { // 每趟路线都是回路,所以可以把每个公交车抽象成一个点,统计连通的点,构图+bfs |