图的存储与遍历
三种存储方式
- 直接存边（起点、终点、边权），一般用于多次建图
- 邻接矩阵（一般存稠密图）
- 邻接表（适用对一个点的所有出边进行排序）
- 链式前向星（数组链表实现的邻接表）
struct G{
int n, m;
struct qxx{
int to, nex;
int w;
};
vector<qxx> e;
vector<int> head, val;
inline void init(int N, int M){
n=N;m=0;
head.clear();
head.resize(N+5);
val.clear();
val.resize(N+5);
e.clear();
e.resize(M+5);
}
inline void add(int u, int v, int w){
e[++m]=qxx{v, head[u], w};
head[u]=m;
}
#define F(i, g, u) for(int i=g.head[u]; i; i=g.e[i].nex)
}g;
两种遍历方式
- DFS 遍历
- DFS 序列：每个子树对应 DFS 序列的连续段
- 涉及回溯问题（括号序列、栈的历史版本还原）
- BFS 遍历
- 最短路相关问题
- $O(n+m)$ 求所有连通块（染色）
- 求状态图状态转移的最小步骤
- 在有向无权图寻找最小环
- 在边权为0/1的图寻找最短路（双端队列）
基环树
定义
无向图上树加一条边形成一个环。有向图上 n 个点每个点只有一条出/入边，形成只有一个环的树/森林。只有一条出边的是内向基环树，只有一条入边的是外向基环树。
解法
- DFS 找到唯一的环
- 面对基环森林，标记节点是否被访问过
- 环上节点递归前使用另一个 DFS 遍历该节点能到达的所有节点并标记
- 在对去掉环的若干棵子树进行处理时进行另一种标记，判断是否是一棵新的基环树
- 建图时使用并查集
- 面对基环森林，标记节点是否被访问过
- 对环之外的部分按照若干棵树处理（树形DP）
- 考虑与环一起计算（断环为链，线性DP+单调队列优化）
最短路
性质
边权为正的图上任意两点之间的最短路
- 不会经过重复的边和点
- 结点数不会超过 n，边数不会超过 n-1
实现
松弛：更新最短路径 d[v]=min(d[v], d[u]+w)
Dijkstra 算法
实现
- 节点划分已确定最短路点集 S，未确定最短路点集 T，初始都属于T
- 重复以下操作直到 T 集合空
- 从 T 选取最短路长度最小的节点转移到 S
- 对刚加入 S 的节点的所有出边进行松弛
应用
非负权图上求单源最短路 朴素适用稠密图 $O(n^2)$ 堆优化适用稀疏图 $O(mlogn)$
int dis[N], vis[N];
void dijkstra(int st, G& g){
priority_queue<pair<int, int>> h;//默认大根堆，first 采用负数变成小根堆
memset(dis, 0x3f, (g.n+1)*sizeof(int));//全部初始化为无穷大
dis[st]=0;
h.push(make_pair(-dis[st], st));//加入起始点
while(!h.empty()){
int u=h.top().second;
h.pop();
if(vis[u]) continue;//在已确定最短路集 S 中，跳过
vis[u]=1;//加入已确定最短路集 S 中
F(i, g, u){
int v=g.e[i].to, w=g.e[i].w;
if(dis[v] > dis[u]+w){//松弛 u 所有出边
dis[v]=dis[u]+w;
if(!vis[v]) h.push(make_pair(-dis[v], v));
}
}
}
}
Bellman-Ford 算法
实现
若存在最短路，则必存在一个不含环的最短路
- 增加超级源点（到所有点边权为0）帮助判断是否存在负环
- 初始化
- 循环 n 次
- 遍历所有边
- 起点的最短路值为无穷大，则跳过
- 否则对终点进行松弛
- 若这次遍历所有边没有松弛，停止算法
- 遍历所有边
- 第 n 轮循环仍然可以松弛说明起点可以抵达一个负环
应用
任意图求单源最短路，能检测负环 朴素 $O(nm)$ 队列优化最坏 $O(nm)$
int dis[N], vis[N], cnt[N];
bool spfa(int st, G& g){
for(int i=1; i<=g.n; ++i) dis[i]=0x7fffffff;
queue<int> q;
dis[st]=0;vis[st]=1;
q.push(st);
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
F(i, g, u){
int v=g.e[i].to, w=g.e[i].w;
if(dis[v] > dis[u]+w){
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;// 记录最短路经过的边数
if(cnt[v]>=g.n) return false;
/*在不经过负环的情况下，最短路至多经过 n - 1 条边
因此如果经过了多于 n 条边，一定说明经过了负环*/
if(!vis[v]) q.push(v), vis[v]=1;
}
}
}
return true;
}
Flyod 算法
实现
$f[k][x][y]=min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])$
应用
任意图求全源最短路，能检测负环 $O(n^3)$
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);//滚动数组降一维
}
}
}
Johnson 算法
实现
设置一个势能零点，零点到其他点的距离为势能 h[u]，两点距离即势能的差值是一定的，dis[u][v]=w[u][v]+h[u]-h[v]
- 创建超级源点，向所有点连一条边权为0的边
- Bellman-Ford 算法求超级源点的单源最短路 h[u]
- 以每个点为起点，进行 n 次 Dijkstra 算法，松弛操作为 $dis[k][v]=min(dis[k][v], dis[k][u]+w+h[u]-h[v])$
- 最短路长度 $dis[u][v]+h[v]-h[u]$
应用
任意图求全源最短路，能检测负环 $O(nmlogm)$
const int INF=1e9;
int h[N];
bool spfa(G& g){
for(int i=1; i<=g.n; ++i) h[i]=INF;
bool flag=false;//判断一轮循环是否发生松弛操作
for(int i=0; i<g.n; ++i){//循环n+1轮
flag=false;
for(int u=0; u<=g.n; ++u){//跑n个点和虚点0
if(h[u]==INF) continue;////跳过不可达点
F(j, g, u){
int v=g.e[j].to, w=g.e[j].w;
if(h[v] > h[u]+w){
h[v]=h[u]+w;
flag=true;
}
}
}
if(!flag) break;
}
return flag;
}
int dis[N][N];
bool vis[N];
void dijkstra(G& g){
priority_queue<pair<int, int>> q;//默认大根堆，first 采用负数变成小根堆
for(int i=1; i<=g.n; ++i)
for(int j=1; j<=g.n; ++j)
dis[i][j]=INF;
for(int i=1; i<=g.n; ++i){
memset(vis+1, 0, g.n*sizeof(bool));
dis[i][i]=0;
q.push(make_pair(-dis[i][i], i));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;//在已确定最短路集 S 中，跳过
vis[u]=1;//加入已确定最短路集 S 中
F(j, g, u){
int v=g.e[j].to, w=g.e[j].w+h[u]-h[v];
if(dis[i][v] > dis[i][u]+w){//松弛 u 所有出边
dis[i][v]=dis[i][u]+w;
if(!vis[v]) q.push(make_pair(-dis[i][v], v));
}
}
}
}
}
void johnson(){
int n, m;
cin>>n>>m;
g.init(n);
for(int i=1, u, v, w; i<=m; ++i){
cin>>u>>v>>w;
g.add(u, v, w);
}
for(int i=1; i<=n; ++i) g.add(0, i, 0);//添加虚点 0
if(spfa(g)){//存在负环
cout<<"-1\n";
return;
}
dijkstra(g);
for(int i=1; i<=n; ++i){
ll ans=0;
for(int j=1; j<=n; ++j){
if(dis[i][j]==INF) ans+=1ll*j*INF;
else ans+=1ll*j*(dis[i][j]+h[j]-h[i]);
}
cout<<ans<<"\n";
}
}
树上问题
树基础
定义与性质
- 无根树（无固定根节点），有根树
- 森林、生成树（连通无向图的生成子图）、无根树的叶节点（度数<=1），有根树的叶节点（无子节点）
- 有根树
- 根节点、子节点、父亲、祖先、兄弟、后代、子树、节点深度、树高度
- 特殊的树
- 链、菊花（星星）、有根二叉树、完整二叉树（full 0/2）、完全二叉树（complete）、完美二叉树
树的存储
- 只记录父节点（适用自底向上递推问题）
- 邻接表（链式前向星）
- 左孩子右兄弟表示法（一般树转二叉树）
树的遍历
- 树上DFS
- 求节点深度、父亲等信息
- 先/中/后序（根节点处理顺序）
- 已知中序和先/后序可求树
- 先序第一个是 root ，后序最后是 root
- 先定根，然后根据中序遍历，根左为左子树，根右为右子树
- 对每个子树可视为全新的树，重复上述操作
- 已知中序和先/后序可求树
- 树上BFS
- 求节点深度、父亲、最短路等信息
- BFS序是树的层序遍历
- 无根树遍历：记录来自哪个节点，避免回头
