数据结构与算法
基础结构
数组
链表
Trie树
基本算法
双指针
- 快慢指针
排序算法
分治
贪心
动规
基本dp
状态压缩dp
树形dp
图论
基本数据结构
- 邻接表
- 适用于稀疏图
- 适用于需要遍历边的情况
- 邻接矩阵
- 适用于稠密图
- 适用于需要快速获取两点之间权值的情况
基础算法
- BFS
- DFS
最短路径
单源无权最短路径
- BFS
单源带权最短路径
对于有负环的有向图，一定无法通过传统算法找到最短路径，路径可以一直减少到负无穷（一直在环内循环）
对于有负权边的无向图，也一定无法通过传统算法找到最短路径，因为无向图向有向图（转换为双向有向图）转变时会产生负环
Dijkstra算法
原理
- 贪心思想，采用优先队列，每次从加入点集的顶点中取出代价最小的点，将其从优先队列弹出，且标记为visit， 并用该点松弛与该顶点直接连接的顶点，如果可以被松弛且visit标志不为true，则加入优先队列中
特点
- 每一次优先队列的弹出操作都已经找到了起点到弹出点的最短路径，所以最多弹出n 次（实际上由于点可能会被重复添加，故最差应该等于边数）即可找到起点到所有点的最短路径
时间复杂度
- 顶点可能被添加到优先队列中的次数最多为边数，因为每条边最多被访问两次，故为O(ElogE)，此时每次要判断当前弹出节点对应的权值是否已经被确定为最优，如果已经被确定了则跳过
- 实际上在手动实现优先队列时能达到IO(ElogV)，用unordered_map存储节点在优先队列中的索引，再通过索引更新权值，更新之后再更新unordered_map中对应的索引
适用性
- 该算法只适用没有负权的带权最短路径问题
- 对于带有负权边的有向无环图（DAG），可以使用可重入的Dijkstra算法，即不用visit数组表示该点是否已经被确定为最优，只要可以松弛即加入优先队列，一直到队列为空，此时对于带有负环的有向图，则会无限循环，此时可以根据某个点加入队列的次数判断是否有环（一个节点进入队列n次一定有环，因为n次松弛在有向无环图中代表经过了n个节点，节点最多有n个）
算法实现（基于C++ STL的priority_queue）
1
2
3
4
5#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}Bellman-Ford
- 原理
- n个节点最多被松弛n次即可达到最短路径
- 特点
- 采用n次循环的方式遍历每一条边，当遍历完成即可得到源点到所有点的最短路径，因为每次松弛都可以得到最短路径上的一个节点， 而一条最短路径最多经过n个节点
- 在有负权边的有向无环图中变现良好
- 原理
SPFA
- 原理
- 优化的Bellman-Ford，只将松驰过的节点加入到队列中，因为本次如果没有松弛该节点，则该节点就是被松弛过且已经使用该节点松驰过其他节点，再次加入队列没有意义；其中对于队列中已经存在的节点只做松弛，不加入队列，因为队列中放的是点集，松弛即更新dist数组，则弹出该节点就用的是最新的权值
- 特点
- 在有负权边的有向无环图中变现良好
- 原理
多源带权最短路径
- Floyd-Warshall
关键路径
- 待学习
连通性
- 并查集
最小生成树
- Prim
- Kruskal
AOE/AOV网
- 拓扑排序
最大流及费用最大流
- 待学习