526互联

【重学OI】图论大礼包

发布时间 2023-10-20 11:29:12作者: exut

继上次数学大礼包之后，再度推出图论

出于一定的功利性以及必要，我们部分基本用不到的算法不会提到

本篇没说题号默认就是洛谷有模板题

本文尽可能略去证明，目的就是复习

对于图的储存，我们不讲，代码里一般是用链式前向星(不会bilibili搜索不分解的AgOh)

part0 概念

图：一张图 \(G\) 由若干个点和连接这些点的边构成。称点的集合为点集 \(V\)，边的集合为边集 \(E\)，记 \(G=(V,E)\)

阶:一张图点集大小 \(|V|\) 称为图的阶

无向图和有向图:图的边有方向/没方向，无向图的边可以视为两条方向相反的有向边

重边:两(多)条端点(和方向)相同的边，无向图中忽略方向

自环:自己向自己连边

相邻:两个点直接相连(无向图中) 则称他们相邻

邻域:无向图中一个点所有的相邻点的集合，记作 \(N(u)\)

邻边:无向图，一段是 \(u\) 的边是 \(u\) 的邻边

度数:一端是 \(u\) 的边的数量，记作 \(d(u)\)，自环贡献为2

入度/出度:有向图，从 \(u\) 出发/到达 \(u\) 的边数

途径:链接一串节点的序列，记作 \(v_0 \to v_1.....\to v_n\)，其中边为点数减一

迹:不重复经过某边的途径

回路:起点终点相同的迹

路径：不经过重复点的迹称为 路径，也称 简单路径。不经过重复点比不经过重复边强，所以不经过重复点的途径也是路径。注意题目中的简单路径可能指迹。

环:除起点终点外其余点都不同的回路

连通:(无向图)存在起点为 \(u\) 终点为 \(v\) 的途径则称 \(u,v\) 连通

简单图：不含重边和自环的图称为 简单图。

DAG：有向无环图

稠密图:边远远多于点的图，通常指 \(m\) 约等于 \(n^2\) 的时候

稀疏图:反之，边和点差不多的图

一些没啥用的待补充，遇到了就写上

part 0.5 基础

默认你会 dfs bfs

拓扑排序

拓排的目的是基于一个DAG制造一个序列 \({p_i}\) 使得在原图中满足每条边的起点在序列中比终点更靠前

形式化地，对于边 \(u\to v\)，设 \(q_i\) 表示 \(i\) 在 \(p\) 中的位置，则 \(q_u \lt q_v\)

首先，可以保证存在这样一种方案(不存在就有环)，DAG的性质是非常好的

通常基于bfs或dfs解决

dfs 较为麻烦，我们给出bfs的方案也是最常见的写法

  • 用队列维护所有入度为 \(0\) 的点，取出队首，删除从 \(u\) 出发所有的边。若某一边终点 \(v\) 在删除后入度变成 \(0\) 就入队，初始把所有入度为 \(0\) 的入队

code:

void topu(){
	for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		sst[++nz]=u;
		for(int i=hd[u];i;i=e[i].nxt){if((--in[e[i].v])==0) q.push(e[i].v);}
	}
}

注意到一张DAG的拓扑序显然是不唯一的，除非及其特殊，拓扑序计数无法做到poly复杂度

拓扑序可以延伸各种奇怪问题

  • 拓扑序 DP，即在拓扑序上通过 DP 的方式统计答案。通常就是在拓排过程中执行dp

  • 最小/大字典序拓扑:bfs时换成优先队列

  • 结合缩点，这个晚点再说

DAG良好的性质使得有非常多优秀的操作

无向图dfs树

对于给定无向连通图 \(G\)，从某一点 \(r\) 开始dfs，不走重复点，最后所经过的点和边显然会形成树形结构。

定义某点的 时间戳 为它在dfs时是第几个被访问到的，简称为DFN。dfs所得到的节点序列称为DFS序

其中某点的时间戳即为它在序列中下标

显然的，dfs树也是不唯一的，树一样时间戳也不唯一

在dfs树上的边称为树边，否则称为非树边

无向图 DFS 树的性质（非常重要）：

  • 祖先后代性：任意非树边两端具有祖先后代关系。

  • 子树独立性：结点的每个儿子的子树之间没有边。

  • 时间戳区间性：子树时间戳为一段区间。

  • 时间戳单调性：结点的时间戳小于其子树内结点的时间戳

part1 最短路

到了笔者之前的噩梦了......

首先明确什么是最短路径问题？

最短路问题简称SPP，研究对象是路径

首先给出如下定义:

  • 带权图:默认指边带权值的图，边权非负则称非负权图，其余同理，实际上有时候也是带点权

  • 边权：边的权值。记作 \(w_{u,v}\)，不带权可以认为就是边权为 \(1\)

  • 路径长度:路径上边权和

  • 负环:长度为负数的环

  • 最短路:称 \(s\to t\) 的最短路为最短的连接 \(s、t\) 的路径，若不可达或不连通则不存在，即最短路无限长；若路上存在负环也不存在，即最短路无穷短

  • 通常 \(s\) 指起点 \(t\) 终点

单源最短路

令 \(dis_i\) 表示 \(s\to i\) 的路径长，则求 \(dis_t\)

这类问题的第一步是把 \(dis_s\) 设为 \(0\) 而 其余设为 inf(极大值)

Bellman-Ford

在此我们首先给出所谓松弛的定义

我们已知 \(dis_u\) 和 \(w_{u,v}\)，那么我们可以用这两个量去更新 \(dis_v\)，即

\[dis_v=min(dis_v,dis_u+w_{u,v}) \]

正确性显然。那么一种可以考虑的方式是:

我们枚举每一个点 \(u\) 和一个可由它到达的点 \(v\)，然后对其松弛

问题来了，松弛几轮？一轮显然无法彻底找出答案

在 \(s\) 到 \(t\) 最短路 \(s\to p_1 \to p_{i=1\to k}....\to t\) 上对于每个 \(p_k\)，\(s\) 到 \(p_k\) 的路径一定是最短路

也就是说一条最短路一定由去掉它的终点的最短路更新而来，而最短路最长为 \(n-1\)，所以松弛 \(n-1\) 轮是必要的

伪代码:

void b_f(){
  初始化略
  for(i=1~n-1){
	for(u=1~n){
      for(u可以通向v ){
		dis[v]=min(dis[v],dis[u]+w(u,v) )
	  }
	}
  }
}

正常情况此时就可以了，当然有个小优化:如果一整轮松弛一次没成功，直接跳出循环

同时，若第 \(n\)轮循环还松弛成功，说明原图存在负环

复杂度 \(O(nm)\)

SPFA

关于SPFA，它死了

SPFA是bf的队列优化，思想在于松弛 \(u\) 时，成功的点加入队列(只有这些点可以继续造成贡献)，已在队中不入队

这个算法是个顶级笑话。号称优化，其实在随机的图里跑的确实飞快，但是在特定数据下会退化和bf一样的 \(O(nm)\)

尽管如此，比下面的 dij好理解的它依然是新手骗分首选

不伪的代码:

void SPFA(){
	for(int i=0;i<=n;i++) dis[i]=inf;
	q.push(s);vis[s]=1,dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			if(dis[v]>dis[u]+G[u][i].w){
				dis[v]=dis[u]+G[u][i].w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}

当然，SPFA也可以判负环。记录一个数组表示当前到某点最短路上边数，松弛成功时对应增加，若大于 \(n\) 则有负环

代码:

void SPFA(){
	for(int i=0;i<=n;i++) dis[i]=inf;
	q.push(s);vis[s]=1,dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].v;
			if(dis[v]>dis[u]+G[u][i].w){
				dis[v]=dis[u]+G[u][i].w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n){
					负环
				}
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}

dijskra

市面上最常见最短路算法，的确他也是最优的

我们考虑到前面的最短路算法都是基于搜索(广搜)的，其实我们也可以基于一个大家都喜欢的算法:贪心

每次寻找当前离源点最近的点(没进行松弛过的)去松弛，没了

复杂度 \(O(n^2+m)\)

等等， \(n、m\) 同级的时候这和某个死掉的算法没啥区别啊！

诶，雀氏。无法体现优越性。但是在稠密图上这个是最优的

code:

点击查看代码 
bool loc[10005];
void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=INT_MAX;
	}
	dis[s]=0;
	while(!loc[c]){
		loc[c]=true;
		for(int i=head[c];i;i=e[i].next){
			if(!loc[e[i].to] and dis[e[i].to]>dis[c]+e[i].aw)
				dis[e[i].to]=dis[c]+e[i].aw;
		}
		int minn=INT_MAX;
		for(int i=1;i<=n;i++)
			if(!loc[i] and minn>dis[i])
				minn=dis[i],c=i;
	}
}

但是就到此为止了吗?没有在稀疏图上更优秀的做法，吗?

所幸，dij可以优化

看到我们代码中的这一段

for(int i=1;i<=n;i++)
	if(!loc[i] and minn>dis[i])
		minn=dis[i],c=i;

干什么用的?找出当前可用的最近点去更新

仔细想想这里也是复杂度瓶颈所在，外层 while 是死的 \(O(n)\) 不可能去掉，这里能不能优化?能不能直接找到最值?

这时候就涉及到一个非常奇妙的数据结构:堆

但是，但是就是说，为了优化最短路写一个堆多半脑子有病

无所谓，priority_queue 会出手

考虑一个小根堆，记录最小值和编号，用值比较

开个结构体重载运算符或者pair就好，个人不喜欢pair所以手写

点击查看代码 

struct node{
	int u,d;
	bool operator<(const node &c)const{
		return c.d<d;
	}
};
int dis[114514];
void dij(){
	for(int i=1;i<=n;i++) dis[i]=INT_MAX;
	dis[s]=0;
	priority_queue<node> q;
	q.push((node){s,0});
	while(!q.empty()){
		int u=q.top().u,d=q.top().d;
		q.pop();
		if(dis[u]!=d) continue;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[u]+w<dis[v]) dis[v]=dis[u]+w,q.push((node){v,dis[v]});
		}
	}
}

实现上注意一个细节:一个点很可能被多次入队，而不同时间入队后的dis也不一样，如果发现队首元素的 \(dis\) 已经存在并且和队首记录的 \(dis\) 不相等就 跳过，这一步称为 懒惰删除 ，没有这一步优先队列dij是假的

复杂度是 \(O(mlogm)\)，用手写堆可以做到 \(mlogn\)，斐波那契堆可以做到 \(nlogn\) (这个只是据说我不确定，存疑)

需要注意的是，在有负数边的时候不可以使用dij，dij的正确性只在正权图保障，否则答案会错

小拓展: 假如边权只有01，我们可以使用双端队列代替优先队列做到线性复杂度

差分约束问题

除了负环，还有一个问题是不能用dij解决的，必须用我们亲爱的SPFA

给出若干组形如 \(x_a-x_b \le c\) 的不等式，求一组合法的 \(x\)

乍一看这个玩意和图论半点关系没有

稍微变形以下 \(x_a+c \ge x_b\) (这里 \(x_a、x_b\) 和上面反的)

你会发现这个玩意和我们松弛的条件很相似

松弛的式子: \(dis_u + w(u,v) \ge dis_v\)

太好力那我们直接把不等式还原成边跑dij不就好了，跑出来 \(dis\) 就是合法的解

等一下，\(c\) 可以是负数，因为若 \(c\) 全为正那我们直接令 \(x\) 全部相等显然就是一组解

啊那我们跑SPFA是不是就可以了

再等等，还有一个小问题，图可能不连通，咋办

不妨设一个初始源点 \(0\) 从 \(0\) 向所有点连一条长度为 \(0\) 的边

为什么这样可以？其实等价于设了一个点 \((x_0 = 0)+0\ge 0\)

也就是要求所有解小于等于 \(0\) ，而对于任意一组解得 \(x\) 全部加上常数 \(A\) 显然依然是解，所以这样是可以的

并且这样求的是 \(x\le 0\) 的字典序最大解

然后愉快的SPFA

模板题code:

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
struct Gra{
	int to,w,nxt;
}G[114514];
int head[114514],tot,cnt[114514];
void add(int u,int v,int w){
	G[++tot]=(Gra){v,w,head[u]};
	head[u]=tot;
}

int dis[114514],n,m;

bool vis[114514];

stack<int> q;

bool SPFA(int s){
	dis[s]=0;
	vis[s]=1;
	cnt[s]++;
	q.push(s);
	while(!q.empty()){
		int u=q.top();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=G[i].nxt){
			int v=G[i].to;
			if(dis[v]>dis[u]+G[i].w){
				dis[v]=dis[u]+G[i].w;
				if(!vis[v]){
					q.push(v);
					cnt[v]++;	
					vis[v]=1;
					if(cnt[v]>n) return 0;
				}
			}
		}
	}
	return 1;
}

int main(){
	cin>>n>>m;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	for (int i=1;i<=m;i++) {
		int opt,a,b,c;
		cin>>a>>b>>c;
		add(b,a,c);
	}
	for (int i=1;i<=n;i++)
		add(n+1,i,0);
	bool z=SPFA(n + 1);
	if (!z) {
		cout<<"NO";
	}
	else{
		for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
	}
	return 0;
}

全源最短路

Johnson意义不大略去不讲了

Floyd

我们可以基于各种东西跑最短路，那 dp 为什么不行

设状态 \(f[i][j]\) 表示 \(i\) 到 \(j\) 的最短路径长度

我们可以枚举一个中间点 \(k\) 然后用 \(f[i][k]+f[k][j]\) 去松弛

特别注意，最外层先枚举中间点

代码:

点击查看代码 
for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
		}
	}
}

考场骗分必备

再考虑另外一个问题:若我们不在乎最短路长度，只在乎两点是否连通，我们怎么解决?

啊对对对，这个问题就是

传递闭包

问题描述见上

诶，我会 floyd

设 状态 \(f[i][j]\) 为 \(i、j\) 是否连通

转移就是 f[i][j]|=f[i][k]& f[k][j]

暴力代码咱就不放了大家都会

有木有更好的做法呢?

我们存在一个优化:bitset

具体过程，可以参考 floyd 算法。即枚举 \(i,j\)，如果某点 \(j\) 可以到达

\(i\) 又可以到达 \(j\) 那么 \(j\) 可达的点 \(i\) 也可达

怎么快速求设一个数组 \(f[i][j]\) 表示点 \(i\) 能不能到 \(j\)

但是这样没有优化，或者说不优

考虑用bitset代替 \(f[i]\) ，那么我们可以用bitset自带的 或 运算解决

复杂度 \(O(\frac{n^3}{w})\) 其中 \(w\) 是压位位数

code:

点击查看代码 
bitset<110> f[110];
void floyd(){
	for(int j=1;j<=n;j++){
		for(int i=1;i<=n;i++){
			if(f[i][j]) f[i]|=f[j];
		}
	}
}

bitset这个科技还是非常好用的并且压位可以带一个几十分之一的常数

后续会说，稀疏有向图可以做到 \(\frac{nm}{w}\)

part2 最小生成树

本章节讨论 无向连通图

相关定义:

生成树:从一个图选所有点若干边组成一棵树

非连通图不存在生成树，但是存在生成森林

不在生成树上的边叫非树边

最小生成树MST问题

即寻找边权和最小的生成树

Kruskal

考虑一条链接 \(u\) 和 \(v\) 的简单路径和一条非树边 \((u,v,w)\) 假若简单路径上存在一边边权大于 \(w\) 那么如果

选择这条非树边更优且合法，也就是说

在最小生成树中，对于任意非树边 \((u,v,w)\)，树上连接 \(uv\) 简单路径上不存在边权大于 \(w\)

这是最小生成树的基本性质

借由这个奇妙性质，我们发现可以把边排序，从小到达依次加入生成树，用并查集维护连通，若当前边两边端点不连通就加入

复杂度 \(O(mlogm+)\) 是最好写最常用的MST算法

同时还有kruskal重构树这一强大应用，稍后提到

代码太简单就不放了

prim

说实话这个玩意比较不常用，因为大部分情况跑不过前面那位还难写一些，稠密图也跑不过下面那位，emmm

设一个点 \(v\) 权值 \(c_v\) 表示 \(v\) 所有邻边中非 \(v\) 那一端在当前生成树中的最小边权

每次取出不在生成树中权最小的点加入并把生成树答案加上 \(c\)

复杂度同不优化dij

考虑可以和dij一样优化到 \(O(mlogm)\)

代码改改dij就是了

Boruvka

通常我们叫他"那个B算法"()

这个算法通常没用并且咱也不喜欢，常数大在有时候还不如kruskal，不展开

part 3 无向图连通性:双连通分量

无向图和有向图连通性中的双连通和强联通分量在图论刷怪中期非常重要，必须掌握

本节没说默认指无向连通图

相关定义:

  • 分量:xx分量，即满足某性质的最大的子图，这里最大指不可以再向四周扩张，扩展后不满足性质

  • 割点:删去某点后连通分量数会增加则是割点

  • 割边:删去某边连通分量数会增加则是割边，也叫桥

  • 点双/边双连通图:不存在割点/割边的连通图

  • 点/边双连通:两点在同一点双/边双。连通分量中

将某种连通分量根据等价性或独立性缩成一个点的操作叫做 缩点

包括:圆方树、边双缩点、强联通缩点

边双性质

结论：两点之间任意一条迹上的所有割边，就是两点之间的所有必经边。

传递性:若 \(a\) 和 \(b\) 边双连通， \(b\) 和 \(c\) 边双连通， \(a\) 和 \(c\) 就边双连通

结论: \(u\) 和 \(v\) 之间边双连通的充要条件是不存在必经边

结论:边双内任意一点或边都有经过其的回路

点双性质

结论:

两点间任意路径的所有割点就是必经点

需要注意，点双之间可以存在公共点
，所有不具备传递性

若两点双有交，则只有一个交点且交点为割点

一个点是割点当且仅当它属于超过一个点双

由一条边直接相连的两点点双连通

如果给每个边双设一个代表点并向割点连边，即会形成一种树形结构，我们称为 块割树(略微不同于圆方树)

一个割点的求——tarjan

前置知识：DFS 树，DFS 序

DFS 序表示对一张图 DFS 得到的结点序列，而时间戳 DFN 表示每个结点在 DFS 序中的位置

在后续，\(x\) 的子树就是指 \(x\) 在dfs生成树上的子树，表述为 \(T(x)\)，而树外的部分记作 \(T'(x)\)

我们需要分开考虑根节点和非根

非根节点的割点判断

此时显然 \(T'(x)\) 非空

不妨先假设 \(x\) 就是割点

那么子树内存在节点 \(y\)

\(y\) 不经过 \(x\) 只能到达子树内

不妨交换假设和结论

若子树内存在一点 \(y\) 满足 \(y\) 不经过 \(x\) 所到达点全部在 \(T(x)\) 内，那么 \(x\) 为割点

(注意不是所有而是存在，自己画一个两个环中间是割点的图模拟以下)

这个玩意可以证明，但略去

转化成代码可以写的语言怎么搞

注意到 \(y\) 若不过 \(x\) 与 \(T'(x)\) 连通那么存在 \(y\) 到 \(T'(x)\) 的路径

假设 \(v\) 是路径上第一个属于 \(T'(x)\) 的节点，\(v\) 就是路径的终点(可以继续延长但 对于我们的算法而言没必要)

则倒数第二个节点设为 \(u\)， \(u\in T(x)\)

假设边 \((u,v)\) 是树边，那么 \(u\) 就是 \(x\) 与假设不符

故 \((u,v)\) 是非树边， \(u\) 是 \(v\) 的后代，所以 \(v\) 也是 \(x\) 的祖先

设 \(d_x\) 为 \(x\) 的时间戳，则有 \(d_x>d_v\)

条件可以写为 \(f_u<d_x\) 其中 \(f_u\) 为 \(u\) 过非树边相连的点中时间戳最小值

我们可以得出非根的割点判法则:

\(\exists y'\in son(x):\min\limits_{u\in T(y')} f_u \ge d_x\)

假设 \(g_x\) 表示 \(x\) 子树内所有点 \(u\) 的 \(f_u\) 最小值

可得:

\[g_x=\min(\min\limits_y'\in son(x) g_{y'},\min\limits_{(x,y)\in E}) \]

(右半柿子还要保证非树边)

特别注意，在推柿子时我们认为右半边需要保证非树边，实际不需要也不导致错误，但是割边需要

\(g_x=d_x\) 在初始

根

假设有两个及以上儿子显然是，否则不是

根据子树独立性，显然

于是就可以得出完整代码:(\(low\) 即为 \(g\))
这篇代码偷懒是vector存图

戳我谢谢 
void taryan(int id){
  dfn[id]=low[id]=++dn;
  int son=0;
  for(auto it:e[id]){
    if(!dfn[it]){
      son++,taryan(it);
      low[id]=min(low[it],low[id]);
      if(id!=R and low[it]>=dfn[id]){cnt+=!cut[id],cut[id]=1;}
    }
    else low[id]=min(low[id],dfn[it]);
  }
  if(son>=2 and id==R)cnt+=!cut[id],cut[id]=1;
}

还是taryan但是割边

推不动了，结论:把大于等于换成大于

但是注意，重边要当成两条边

懒得写