图论

DFS

• DFS是回溯算法的一种特例

• DFS最重要的是确定遍历顺序

BFS

• 思路：从起点开始，往前走第一步，记录下所有第一步能走到的点，然后从所第一步能走到的点开始，往前走第二步，记录下所有第二步能走到的点，重复下去，直到走到终点

• BFS利用队列实现，因为队列先进先出的特性可以很好地实现先进入点先出队列

• BFS常用于边权相同的最短路问题

树与图的存储

• 稠密图：点的数量的平方 远远小于 边的数量--------邻接矩阵存储

• 稀疏图：点的数量的平方 近似等于 边的数量--------邻接表存储

• 无向图：存储时，两点之间存储两条有向边

• 有向图：存储时，两点之间根据题目情况存储边数，一般存储一条有向边，除非有重边的情况

• 树：存储时，可以看成是特殊的图

拓扑排序

• 拓扑序：

• 拓扑排序可以判断有向图中是否有环，可以生成拓扑序列

Kahn（卡恩）算法（必须掌握）

DFS算法（拓展了解）

单源最短路

Dijkstra（迪杰斯特拉）算法

• Dijkstra算法是基于贪心思想的单源最短路算法

• 算法步骤

❗

提高：朴素版的Dijkstra算法适用于稠密图，但是碰到稀疏图时可能会超时，所以这时候就需要堆优化版的Dijkstra算法了

• 我们观察朴素版的代码可以发现，算法的时间浪费在：每一次都要从所有的点中找出距离起点最短的点

• 使用堆优化之后，可以使用距离负数的大根堆来存储距离和点，从而将这一找距离最短点的操作减短至O（1）

❗

通过点与边的关系，区分：

• 稀疏图——邻接表——堆优化Dijkstra算法

• 稠密图——邻接矩阵——朴素版Dijkstra算法

Bellman-ford算法

❗

Dijkstra算法无法解决边权含负值的情况

• dijkstra要求每个点被确定后st[j] = true，dist[j]就是最短距离了，之后就不能再被更新了（一锤子买卖），而如果有负权边的话，那已经确定的点的dist[j]不一定是最短了

❗

1. backup干啥使的 backup[j]表示每次进入第2重循环的dist数组的备份。 如果不加这个备份的话有可能会发生节点最短距离的串连； 比如说：

现在从3号结点走到4号节点要想进行松弛操作就必须先得到dist[3]，要想得到dist[3]就得知道dist[2]； dist[2]=2，现在dist[3]是正无穷，用2号结点来更新3号结点，dist[3]=2+3=5;

现在要更新dist[4]了，此时dist[4]=正无穷

出现问题了，dist[4]是用dist[3]是用正无穷来更新还是5呢

用dist[3]=5来更新那是下一次i迭代的事情； 这道题说是不经过k条边，说不定下一次就到k条边了，所以还是得用正无穷来更新的

2.怎么返回呢还是这样吗？

比如说这样：

这个奇葩起点和终点居然不连通

4号点在经过松弛操作后可能会更新5号点，因为正无穷-2<正无穷吗；

所以终点就不是正无穷了，所以就返回正无穷-2了，不对

又因为如果正无穷减也不会减的太大（数据保证边权的绝对值不大于100000）

所以就直接这样写

最小生成树

最近公共祖先

两个节点的最近公共祖先（LCA）就是这两个点的公共祖先里面，离他们最近的那个。

倍增算法是最经典的求LCA算法

1. dfs一遍，创建ST表
倍增递推：fa[u][i] = fa[fa[u][i - 1]][i - 1]

2. 利用ST表求LCA
• 将u,v跳到同一层



• 将u，v一起跳到LCA的下一层