前言

这是有关于图论的一篇文章。主要包括：

1. 图论知识点与模板代码
2. 一些经典题目的讲解
3. 一些做题的 trick

part 1 图的存储与遍历

图的存储

主要有三种方式存图：

1. 邻接矩阵
2. 邻接表 （可用 stl 中 vector 实现）
3. 链式前向星 （用链表实现）

其中，邻接矩阵用于图较小的情况，通常用邻接矩阵时要用 floyd 算法。一般图是用邻接表存

空间复杂度： 邻接矩阵复杂度为 $O(n^2)$ ，邻接表与链式前向星复杂度为 $O(n + m)$

图的遍历

图有两种遍历方式：

1. dfs （深度优先搜索）
2. bfs （广度优先搜索）

dfs 在图中主要是用于记忆化搜索和暴力寻找路径，bfs 在图中主要是用于求最短路(见后文)

时间复杂度：都为 $O(m)$

列题

P2921 Trick or Treat on the Farm G

part 2 最短路

求最短路主要有以下算法

1. $dijkstra$ 算法，用于没有负权边的图
2. $spfa$ 算法，用于有负权边，但没负环的图
3. $bellman-ford$ 算法，用于有负权环的图，一般有边数限制
4. $floyd$ 算法，求全源最短路

其中，如果边权全部为 $1$ , 则可用 bfs 处理最短路

dijkstra 算法

$dijkstra$ 算法 过程

1. 准备步骤 ： $vis$ 数组，判断节点是否已经松弛邻居节点；$dis$ 数组，存从起点到每一个点的距离；$q$ 优先队列，快速找最小值

2. 初始化 $dis_s = 0$ , $s$ 为起点，其余节点的值为 $inf$

3. 将 $q$ 的堆顶 $x$ 取到，弹出 $x$，此时 $x$ 为 $dis$ 值最少，注意如果 $x$ 被标记要 continue，表示此时 $x$ 的邻居节点已经被 $x$ 松弛

4. 从 $x$ 出发，遍历 $x$ 的所有子节点，若 $dis_y > dis_x + w$，则使用 $dis_x$ 更新 $dis_y$ 这一步叫做松弛，如果 $y$ 还没有被标记，入队，否者不管

时间复杂度 ： $O((n + m)\log n)$，朴素算法：$O(n^2)$

code:

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;

struct edge{
	int to , w;
};

struct node{
	int id , p;
	
	bool operator <(const node &lhs)const &{
		return p > lhs.p;
	}
};

int n , m , s , dis[N] , vis[N];
vector<edge> g[N];

void dijsktra(){
	for(int i = 1 ; i <= n ; i ++){
		dis[i] = inf;
	}
	dis[s] = 0;
	priority_queue<node> q;
	q.push({s , 0});
	
	while(!q.empty()){
		node u = q.top(); q.pop();
		if(vis[u.id]) continue;
		vis[u.id] = 1;
		
		for(int i = 0 ; i < g[u.id].size() ; i ++){
			edge v = g[u.id][i];
			if(vis[v.to]) continue;
			if(dis[v.to] > v.w + u.p){
				dis[v.to] = v.w + u.p;
				q.push({v.to , dis[v.to]});
			} 
		}
	}
}

注意如果用的结构体的话要重载 $<$ 运算，因为小根堆是用的 $<$做的比较

扩展应用：

1. 可用于图上的 dp 转移
2. 优先队列一开始入队多个点，求一个点到给顶所有点的最短距离

floyd 算法

$floyd$ 是一种动态规划算法：

1. 状态设计：$dis_{x,y}$ 表示 $x,y$ 间的最短路

2. 初始化：若由边连接 $x,y$，边权为 $w$ , 则 $dis_{x,y} = w$ , $dis_{x,x} = 0$ (自己到自己的距离为 $0$)

3. 状态转移方程：$dis_{x,y} = \min(dis_{x,y},dis_{x,k} + dis_{y,k})$

4. 转移顺序，只用注意一点，先枚举 $k$ 即可

时间复杂度：$O(n^3)$

code：

	for(int k = 1 ; k <= v ; k ++){
		for(int i = 1 ; i <= v ; i ++){
			for(int j = 1 ; j <= v ; j ++){
				dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
			}
		}
	}

分层图上的最短路

其实可以把 dijkstra 算法近似看作为一种动态规划算法（严格来说并不是，因为 dijkstra 算法的转移并无最优子结构性质），其中的状态即节点，最短路即动态规划的最优解。而转移过程则是在图上由优先队列构建，从已遍历节点中选取权值最优，扩展到邻居的过程

用了以上思想，便可以理解在分层图上的最短路和 dp 了，简而言之，分层图就是将一个点拆为很多种状态，随后按照一定的转移方式在图上做 dp 即可

在图上的 dp 主要转移方式有以下几种：

1. dfs 序，适用于树或在图上做记忆化搜索
2. 拓扑序，适用于 DAG 或一些满足拓扑偏序的状态设计
3. dijkstra 序，一般即 bfs + 优先队列，适用于正权边的分层图

列题

P1144 最短路计数

P1522 [USACO2.4] 牛的旅行 Cow Tours

P4568 [JLOI2011] 飞行路线

P9751 [CSP-J 2023] 旅游巴士

P5304 [GXOI/GZOI2019] 旅行者

P4001 [ICPC-Beijing 2006] 狼抓兔子

part 3 最小生成树

最小生成树是指在图上求一颗树，使得 $V_{G} = V_{tree}$，满足其边权之和最小

求最小生成树主要有两种算法：

1. prim 算法 $O(n\log n)$
2. kruskal 算法 $O(m\log n)$

这里只介绍 kruskal 算法

kruskal 算法

kruskal 算法的核心思想是贪心。将所有的边按边权从小到大进行排序，随后依次加入到生成树中，判断加入这条边后树种是否会形成环。若会，则直接 continue；若不会，则将此条边加入树即可

可以用并查集维护上述操作，如果当前加入边数为 $n - 1$ 就退出

code

int find(int x){
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

bool uni(int u , int v){
	int x = find(u) , y = find(v);
	if(x != y){
		fa[x] = y;
		return true;
	}
	return false;
}

void kruskal(){
	for(int i = 1 ; i <= n ; i ++) fa[i] = i;
	
	sort(e + 1 , e + m + 1 , cmp);
	
	for(int i = 1 ; i <= m ; i ++){
		if(uni(e[i].x , e[i].y)){
			idx ++ , sum += e[i].w;
		}else continue;
		
		if(idx >= n - 1) break;
	}
}

瓶颈生成树

瓶颈生成树是指在图上求一颗树，使得 $V_{G} = V_{tree}$，满足其边权的最大值最小

定理：最小生成树是瓶颈生成树的充分不必要条件

即最小生成树一定为是瓶颈生成树，而瓶颈生成树却不一定是最小生成树

列题

P1967 [NOIP 2013 提高组] 货车运输

part 4 拓扑排序

拓扑排序是指在 有向无环图（DAG） 上的一种算法，满足对 $\forall (u,v) \in E$ 有排序后 $u$ 在 $v$ 的前面

实现

拓扑排序一般用 bfs 实现，步骤如下：

1. 统计入度 ind 数组，将图中入度为 $0$ 的点入队
2. 出队点 $u$，将 $u$ 所有相邻的点 $v$ 入度减 $1$
3. 如果点 $v$ 入度为 $0$ 入队，重复直到队列为空

code:

for(int i = 1 ; i <= idx ; i ++){
	if(in[i] == 0) q.push(i);
}

while(!q.empty()){
	int u = q.front();
	q.pop();
	
	for(int i = 1 ; i <= idx ; i ++){
		if(!g[u][i]) continue;
		if(-- in[i] == 0){
			q.push(i);
		}
	}
}

拓扑序

拓扑排序有一个非常广泛的应用：DAG 上 dp

其中 dp 的转移顺序就是拓扑序

eg.

DAG 上最长路径

设 $dp_{u}$ 为到节点 $u$ 的最长路径，有如下转移（dp 按拓扑序转移）：

$$dp_{u} = max(dp_{u} , dp_{v} + w(u , v))$$

随后在每个点中取 $dp$ 最大值即可

列题

[NOIP 2013 普及组] 车站分级

part 5 连通性问题