图论初步

博主： RearWaves
发布时间：2023 年 05 月 09 日
403 次浏览
4 条评论
7616字数
分类：算法设计

# 图论1

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

# 1 树和图的遍历: 拓扑排序

## 1.1 树和图的存储

有向图:$a\to b$

1. 邻接矩阵(适合稠密图),二维数组
2. 邻接表

无向图: 建两条边: $a\to b,\ b\to a$

**存储模板:**

```c++
const int N = 1e5 + 10;	//数据范围是10的5次方
const int M = 2 * N;	//以有向图的格式存储无向图, 所以每个节点至多对应2n-2条边

int h[N];	//邻接表存储树, 有n个节点, 所以需要n个队列头节点
int e[M];	//存储元素,下标为idx时对应的具体的点
int ne[M];	//存储列表的next值
int idx;	//单链表指针,每次有新的边时idx++
bool st[N]; //记录节点是否被访问过, 访问过则标记为true

//插入一条由a指向b的边,a所对应的单链表中插入b,其中a作为根 
void add(int a, int b) {
	//头插法
	e[idx] = b;		//把2保存在e[idx]中
    ne[idx] = h[a];	//2的下一个节点是之前1的头一个元素
    h[a] = idx++;	//把2插入到a为根的链表的头部
}
int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    ......
    return 0;
}
```

举例:现在$h[1]\to 3 \to 4 \to \varnothing \\h[2]\to 1 \to 4 \to \varnothing $ 要插入$1 \to 2$, 使用头插法, 变成$h[1]\to 2\to 3 \to 4 \to \varnothing $.

## 1.2 树与图的深度优先遍历

**遍历模板:**

```c++
void dfs(int u) {
	st[u] = 1;	// 标记一下, 记录为已经被搜索过了, 下面进行搜索过程
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[j];
		if (!st[j]) dfs(j);
		//不需要回溯, 每个点只能被遍历一次, 打上标记的点表示已经被遍历过, 防止以后重复遍历
	}
}
```

### [846. 树的重心](https://www.acwing.com/problem/content/848/)

给定一颗树, 树中包含n个结点(编号1~n)和n-1条无向边.

请你找到树的重心, 并输出将重心删除后, 剩余各个连通块中点数的最大值.

重心定义: 重心是指树中的一个结点, 如果将这个点删除后, 剩余各个连通块中点数的最大值最小, 那么这个节点被称为树的重心.

> **分析:**dfs遍历每一个结点,求该节点删除之后剩余连通图的最大值,在求所有最大值中的最小值.

```c++
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
bool st[N];		//记录节点是否被访问过
int n, ans = N;
//a所对应的单链表中插入b,其中a作为根 
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;

}
//返回以u为根的子树中节点的个数, 包括u节点
int dfs(int u) {
	int res = 0;	//存储 删掉某个节点之后,最大连通子图节点数
	st[u] = true;	//标记访问过的u节点
	int sum = 1;	//存储 以u为根的数 的节点(包括u)
	//访问u的每个子节点
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];	//把节点的值取出来赋值给j
		//这里节点的值就是节点的编号,用编号为下标来标记是否被访问过
		if (!st[j]) {	//判断编号为j的节点是否被访问过
			int s = dfs(j);		//s是以 u的子节点j 为根的树(u的一个子树)的节点数
			res = max(res, s);	//以j为根的树是删除u节点后的一个连通图
			sum += s;			//以j为根的树是 以u为节点的树 的一部分
		}
	}
	//n-sum 是所有的节点中去掉以u为根的树的所有节点
	res = max(res, n - sum);	//选择u节点为重心, 最大的连通子图节点数
	ans = min(res, ans);		//遍历过的假设重心中, 最小的最大联通子图的节点数
	return sum;
}
int main() {
	memset(h, -1, sizeof h);	//初始化数组h,让其全部指向空
	cin >> n;
	//树中是不存在环的, 对于有n个节点的树, 必定是n-1条边
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);	//无向图中一条边相当于两条相互的边
	}
	dfs(1);		//可以任意选定一个节点开始 u<=n
	cout << ans << endl;
	return 0;
}
```

## 1.3 树与图的广度优先遍历

### [847. 图中点的层次](https://www.acwing.com/problem/content/849/)

给定一个n个点m条边的有向图, 图中可能存在重边和自环. 所有边的长度都是1, 点的编号为1~n.

请你求出1号点到n号点的最短距离, 如果从1号点无法走到n号点, 输出-1.

输入格式: 两个整数n和m. 接下来m行, 一条从a走到b的长度为1的边.

输出格式: 输出1号点到n号点的最短距离.

```c++
const int N = 1e5 + 10, M = N * 2;
int n, m;
int h[N], e[M], ne[M], idx = 0;
int d[N], q[N];	//d为各点到第一个点的距离,q为队列
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {
	int hh = 0, tt = 0;
	q[0] = 1;
	memset(d, -1, sizeof d);	//初始化为-1代表没有被访问
	d[1] = 0;
	while (hh <= tt) {
		int t = q[hh++];
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (d[j] == -1) {
				d[j] = d[t] + 1;
				q[++tt] = j;
			}
		}
	}
	return d[n];
}
int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	cout << bfs() << endl;
}
```

## 1.4 拓扑排序

若一个由图中所有点构成的序列A满足: 对于图中的每条边(x, y), x在A中都出现在y之前, 则称A是该图的一个拓扑序列.

**模板:**

```c++
queue <- 所有入度为0的节点;
while (queue 不空) {
	t <- 队头;
	枚举t的所有出边 t-> j:
		删掉 t->j, d[j]--;
		if (d[j] == 0) {
			queue <- j;
		}
}
```

### [848. 有向图的拓扑序列](https://www.acwing.com/problem/content/850/)

给定一个n个点m条边的有向图, 点的编号是1到n, 图中可能存在重边和自环.

请输出任意一个该有向图的拓扑序列, 如果拓扑序列不存在, 则输出-1.

```c++
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int n, m;
int q[N], d[N];	//d表示各个点的入度

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort() {
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0)
			q[++tt] = i;	//入度为0的点入队
	}
	while (hh <= tt) {
		int t = q[hh++];	//在队列中取出一个点t
		//对该点进行BFS
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			d[j]--;			//删除点t指向j的边
			if (d[j] == 0)
				q[++tt] = j;//如果删除后点j的入度为0
		}
	}
	return tt == n - 1;
	//如果所有n个点全部入队,说明该图没有环,是拓扑图,返回true
}
int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
		d[b]++;		//增加一条a到b的边,b的入度加一
	}
	if (topsort()) {
		for (int i = 0; i < n; i++) printf("%d ", q[i]);
		puts("");
	}
	else puts("-1");
	return 0;
}
```

# 2 最短路

设一个图中的点有n个, 边有m条.

当$m$和$n^2$一个级别: 稠密图;

当$m$和$n$一个级别: 稀疏图.

![Hongda_2022-11-26_08-53-00](https://www.rearwaves.com/usr/assets/algorithm/graph/Hongda_2022-11-26_08-53-00.png)

## 2.1 朴素版的Dijkstra算法

![98504cdcddd6d683a91c09357395d12.png](https://www.rearwaves.com/usr/assets/algorithm/graph/0e5b3f689168da7c5c2eca6e3f065618.png)

### [849. Dijkstra求最短路 I](https://www.acwing.com/problem/content/851/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环, 所有边权均为正值. 请你求出 1 号点到 n 号点的最短距离, 如果无法从 1 号点走到n号点, 则输出 ―1 .

```c++
const int N = 510;
int n, m;
int g[N][N], dist[N];	//稠密图,邻接矩阵;到第一个点的举例
bool st[N];		//判断当前的最短路是否已经确定
int dijkstra() {
	//初始化距离,0x3f代表无限大
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;	//第一个点到自身的距离为0
	//n个点,需要进行n次迭代
	for (int i = 0; i < n; i++) {
		int t = -1;
		//找到当前未在s中标记过且离源节点最近的点
		for (int j = 1; j <= n; j++)
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		st[t] = true;	//将最近的点标记
		//用最新标记的t点更新到其他点的距离
		for (int j = 1; j <= n; j++)
			dist[j] = min(dist[j], dist[t] + g[t][j]);
	}
	if (dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];

}
int main() {
	scanf("%d%d", &n, &m);
	//初始化图,0x3f代表无限大
	memset(g, 0x3f, sizeof g);
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c);	//如果发生重边的情况则保留最短的一条边
	}
	int t = dijkstra();
	printf("%d\n", t);
	return 0;
}
```

## 2.2 堆优化的Dijkstra算法

### [850. Dijkstra求最短路 II](https://www.acwing.com/problem/content/852/)

```c++
const int N = 1e6+10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;	//稀疏图, 邻接表
int dist[N];	//到第一个点的举例
bool st[N];		//判断当前的最短路是否已经确定
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra() {
	//初始化距离,0x3f代表无限大
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;	//第一个点到自身的距离为0
	priority_queue<PII, vector<PII>, greater<PII>> heap;	//定义一个小根堆
	//这里heap中为什么要存pair呢, 首先小根堆是根据距离来排的, 所以有一个变量要存距离;
	//其次在从堆中拿出来的时候要知道知道这个点是哪个点, 不然怎么更新邻接点呢？所以第二个变量要存点. 
	heap.push({ 0, 1 });	//初始化,第一个点距离为0,注意pair排序时先根据first排
	while (heap.size()) {
		auto t = heap.top();	//取不在集合S中距离最短的点
		heap.pop();
		int ver = t.second, distance = t.first;
		if (st[ver]) continue;	//如果该点已有最短距离,跳过
		st[ver] = true;		//否则对该点进行标记
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];	//取出点j
			if (dist[j] > dist[ver] + w[i])
			{
				dist[j] = dist[ver] + w[i];
				heap.push({ dist[j], j });
			}
		}
	}

if (dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}
int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	while (m--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	int t = dijkstra();
	printf("%d\n", t);
	return 0;
}
```

## 2.3 bellman - ford算法

**1. 什么是bellman - ford算法:**

Bellman - ford 算法是求含负权图的单源最短路径的一种算法, 效率较低, 代码难度较小. 其原理为连续进行松弛, 在每次松弛时把每条边都更新一下, 若在 n-1 次松弛后还能更新, 则说明图中有负环, 因此无法得出结果, 否则就完成.

**2. 为什么需要back[a]数组:**

为了避免如下的串联情况,  在边数限制为一条的情况下, 节点3的距离应该是3, 但是由于串联情况, 利用本轮更新的节点2更新了节点3的距离, 所以现在节点3的距离是2.

$$
1--(1)--> 2 --(1)--> 3\\|\_\_\_\_\_\_\_\_\_\_\_\_(3)\_\_\_\_\_\_\_\_\_\_\_\_\_|
$$

正确做法是用上轮节点2更新的距离--无穷大, 来更新节点3,  再取最小值, 所以节点3离起点的距离是3.

**3. 为什么是`dist[n]>0x3f3f3f3f/2`,  而不是`dist[n]>0x3f3f3f3f`:**

$$
5--(-2)-->n
$$

5号节点距离起点的距离是无穷大, 利用5号节点更新n号节点距离起点的距离, 将得到109−2109−2, 虽然小于109109, 但并不存在最短路, (在边数限制在k条的条件下).

**模板:**

```c++
for n次
	for 所有边 a,b,w (松弛操作)
		dist[b] = min(dist[b],back[a] + w)
```

### [853. 有边数限制的最短路](https://www.acwing.com/problem/content/855/)

给定一个n个点m条边的有向图, 图中可能存在重边和自环,  **边权可能为负数**.

请你求出从1号点到n号点的最多经过k条边的最短距离, 如果无法从1号点走到n号点, 输出impossible.

注意: 图中可能 **存在负权回路** .

```c++
const int N = 510, M = 10010;
struct Edge
{
	int a, b, c;
}edges[M];
int n, m, k;
int dist[N];
int back[N];	//备份数组防止串联
void bellman_ford() {
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	for (int i = 0; i < k; i++) {
		memcpy(back, dist, sizeof dist);
		for (int j = 0; j < m; j++) {	//遍历所有边
			auto e = edges[j];
			//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
			dist[e.b] = min(dist[e.b], back[e.a] + e.c);
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		edges[i] = { a, b, c };
	}
	bellman_ford();
	if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
	else printf("%d\n", dist[n]);
	return 0;
}
```

## 2.4 spfa算法

**1. 什么是spfa算法？**

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称, 通常用于求含负权边的单源最短路径, 以及判负权环. SPFA一般情况复杂度是O(m)O(m) 最坏情况下复杂度和朴素 Bellman-Ford 相同, 为O(nm)O(nm). **spfa也能解决权值为正的图的最短距离问题, 且一般情况下比Dijkstra算法还好.**

**模板:**

```c++
for n次
	for 所有边 a,b,w (松弛操作)
		dist[b] = min(dist[b],back[a] + w)
```

spfa算法对第二行中所有边进行松弛操作进行了优化, 原因是在bellman—ford算法中, 即使该点的最短距离尚未更新过, 但还是需要用尚未更新过的值去更新其他点, 由此可知, 该操作是不必要的, 我们只需要找到更新过的值去更新其他点即可.

**spfa 图解: **

给定一个有向图, 如下, 求A~E的最短路.

源点A首先入队, 然后A出队, 计算出到BC的距离会变短, 更新距离数组, BC没在队列中, BC入队

B出队, 计算出到D的距离变短, 更新距离数组, D没在队列中, D入队. 然后C出队, 无点可更新.

D出队, 计算出到E的距离变短, 更新距离数组, E没在队列中, E入队.

E出队, 此时队列为空, 源点到所有点的最短路已被找到, A->E的最短路即为8

### [851. spfa求最短路](https://www.acwing.com/problem/content/853/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环, **边权可能为负数**.

请你求出1号点到n号点的最短距离, 如果无法从1号点走到n号点, 则输出impossible .

数据保证**不存在负权回路**.

```c++
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;	//稀疏图, 邻接表
int dist[N];	//到第一个点的举例
bool st[N];		//判断当前的点是否在队列当中
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}
int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);
	return 0;
}
```

### [852. spfa判断负环](https://www.acwing.com/problem/content/854/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环,  **边权可能为负数**.

请你判断图中是否存在负权回路.

**解题思路:**

统计当前每个点的最短路中所包含的边数, 如果某点的最短路所包含的边数大于等于n, 则也说明存在环.

**维护cnt数组的作用:**
记录每个点到起点的边数, 当cnt[i] >= n 表示出现了边数>=结点数, 必然有环, 而且一定是负环！

```c++
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;	//稀疏图, 邻接表
int dist[N], cnt[N];
bool st[N];		//判断当前的点是否在队列当中
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa() {
	//memset(dist, 0x3f, sizeof dist);
	//dist[1] = 0;
	queue<int> q;
	//将所有点进入队列,因为从1出发可能无法到达负环
	for (int i = 1; i <= n; i++) {
		st[i] = true;
		q.push(i);
	}
	while (q.size()) {
		int t = q.front();
		q.pop();
		st[t] = false;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] > dist[t] + w[i]) {
				dist[j] = dist[t] + w[i];
				cnt[j] = cnt[t] + 1;
				if (cnt[j] >= n) return true;
				if (!st[j]) {
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	return false;
}
int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	puts(spfa() ? "Yes" : "No");
	return 0;
}
```

## 2.5 Floyd算法

动态规划: `f[k][i][j]`代表(k的取值范围是从1到n), 在考虑了从1到k的节点作为中间经过的节点时, 从i到j的最短路径的长度.

`f[k][i][j]`可以从两种情况转移而来:

1. 从`f[k−1][i][j]`转移而来, 表示i到j的最短路径不经过k这个节点
2. 从`f[k−1][i][k]+f[k−1][k][j]`转移而来, 表示i到j的最短路径经过k这个节点

### [854. Floyd求最短路](https://www.acwing.com/problem/content/856/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环, 边权可能为负数.

再给定 k 个询问, 每个询问包含两个整数 x 和 y, 表示查询从点 x 到点 y 的最短距离, 如果路径不存在, 则输出 `impossible`.

数据保证图中不存在负权回路.

```c++
const int N = 210;
int n, m, q;
int d[N][N];
void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) d[i][j] = 0;
			else d[i][j] = 0x3f;
		}
	}
	while (m--) {
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		d[a][b] = min(d[a][b], w);
	}
	floyd();
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (d[a][b] > 0x3f3f3f3f / 2) puts("impossible");
		else printf("%d\n", d[a][b]);
	}
	return 0;
}
```

# 3 最小生成树

![Hongda_2022-11-27_14-55-45](https://www.rearwaves.com/usr/assets/algorithm/graph/Hongda_2022-11-27_14-55-45.png)

## 3.1 普利姆算法(Prim)

**模板**

```c++
S:当前已经在联通块中的所有点的集合
1. dist[i] = inf
2. for n 次
    t<-S外离S最近的点
    利用t更新S外点到S的距离
    st[t] = true
n次迭代之后所有点都已加入到S中
//联系: Dijkstra算法是更新到起始点的距离, Prim是更新到集合S的距离
```

举例: 绿色的点为集合S, 下一个加入的点为F, 结果加上边C->F.

![5.png](https://www.rearwaves.com/usr/assets/algorithm/graph/64616_8a24258268-5.png)

### [858. Prim算法求最小生成树](https://www.acwing.com/problem/content/860/)

给定一个 n 个点 m 条边的无向图, 图中可能存在重边和自环, 边权可能为负数.

求最小生成树的树边权重之和, 如果最小生成树不存在则输出 `impossible`.

给定一张边带权的无向图 G=(V,E), 其中 V 表示图中点的集合, E 表示图中边的集合, n=|V|, m=|E|.

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树, 其中边的权值之和最小的生成树被称为无向图 G 的最小生成树.

```c++
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int prim() {
	memset(dist, 0x3f, sizeof dist);	//初始化距离数组为一个很大的数
	int res = 0;
	//迭代n次
	for (int i = 0; i < n; i++) {
		int t = -1;
		//遍历所有的点
		for (int j = 1; j <= n; j++) {
			//如果该点集合外且(当前没有找到任何的点或当前的距离更短)
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		}
		//如果不是第一个点并且距离为正无穷,说明不是连通图
		if (i && dist[t] == INF) return INF;
		//先计算res的值再更新,避免自环影响结果
		if (i) res += dist[t];
		for (int j = 1; j <= n; j++)
			dist[j] = min(dist[j], g[t][j]);
		
		st[t] = true;
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	memset(g, 0x3f, sizeof g);
	while (m--) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	int t = prim();
	if (t == INF) puts("impossible");
	else printf("%d\n", t);
	return 0;
}
```

## 3.2 克鲁斯卡尔算法(Kruskal)

**模板:**

```c++
1. 将所有边按权重从小到大排序
2. 枚举每条边 a,b, 权重是c
if a,b不连通 
	将这条边加入集合
```

### [859. Kruskal算法求最小生成树](https://www.acwing.com/problem/content/861/)

给定一个 n 个点 m 条边的无向图, 图中可能存在重边和自环, 边权可能为负数.

求最小生成树的树边权重之和, 如果最小生成树不存在则输出 `impossible`.

给定一张边带权的无向图 G=(V,E), 其中 V 表示图中点的集合, E 表示图中边的集合, n=|V|, m=|E|.

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树, 其中边的权值之和最小的生成树被称为无向图 G 的最小生成树.

```c++
const int N = 2e5 + 10;
int n, m;
int p[N];	//并查集
struct Edge {
	int a, b, w;
	//重载'<',按照权重排序
	bool operator< (const Edge& W)const {
		return w < W.w;
	}
}edges[N];

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = { a, b, w };
	}
	sort(edges, edges + m);
	//初始化并查集
	for (int i = 0; i < n; i++) p[i] = i;
	int res = 0;	//最小生成树中所有树边的权重之和
	int cnt = 0;	//当前加入的边数
	for (int i = 0; i < m; i++) {
		int a = edges[i].a, b = edges[i].b, w = edges[i].w;
		a = find(a), b = find(b);
		if (a != b) {	//判断a,b是否在同一个连通图中
			p[a] = b;
			res += w;
			cnt++;
		}
	}
	if (cnt < n - 1) puts("impossible");	//不是连通图
	else printf("%d\n", res);
	return 0;
}
```

# 4 二分图

## 4.1 染色法

将所有点分成两个集合, 使得所有边只出现在集合之间, 就是二分图.

二分图: 一定不含有奇数环, 可能包含长度为偶数的环,  不一定是连通图.

### [860. 染色法判定二分图](https://www.acwing.com/problem/content/862/)

给定一个 n 个点 m 条边的无向图, 图中可能存在重边和自环.

请你判断这个图是否是二分图.

**方法一:dfs版本**

染色可以使用1和2区分不同颜色, 用0表示未染色.遍历所有点, 每次将未染色的点进行dfs, 默认染成1或者2.

由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return.染色失败相当于存在相邻的2个点染了相同的颜色.

```c++
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c) {
	color[u] = c;
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (!color[j]) {
			if (!dfs(j, 3 - c)) return false;
		}
		else if (color[j] == c) return false;
	}
	return true;
}
int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	bool flag = true;	//判断染色时是否有矛盾发生
	for (int i = 1; i <= n; i++) {
		if (!color[i]) {
			if (!dfs(i, 1)) {
				flag = false;
				break;
			}
		}
	}
	puts(flag ? "Yes" : "No");
	return 0;
}
```

**方法二:bfs版本**

颜色 1 和 2 表示不同颜色, 0 表示 未染色,定义queue是存PII, 表示 <点编号, 颜色>.

同理, 遍历所有点, 将未染色的点都进行bfs.队列初始化将第i个点入队, 默认颜色可以是1或2.

while (队列不空):每次获取队头t, 并遍历队头t的所有邻边.若邻边的点未染色则染上与队头t相反的颜色, 并添加到队列;若邻边的点已经染色且与队头t的颜色相同, 则返回false.

```c++
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool bfs(int u) {
	int hh = 0, tt = 0;
	PII q[N];
	q[0] = { u, 1 };
	color[u] = 1;
	while (hh <= tt) {
		auto t = q[hh++];
		int ver = t.first, c = t.second;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (!color[j]) {
				color[j] = 3 - c;
				q[++tt] = { j, 3 - c };
			}
			else if (color[j] == c) return false;
		}
	}
	return true;
}
int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	bool flag = true;	//判断染色时是否有矛盾发生
	for (int i = 1; i <= n; i++) {
		if (!color[i]) {
			if (!bfs(i)) {
				flag = false;
				break;
			}
		}
	}
	puts(flag ? "Yes" : "No");
	return 0;
}
```

## 4.2 匈牙利算法

### [861. 二分图的最大匹配](https://www.acwing.com/problem/content/863/)

给定一个二分图, 其中左半部包含 n1 个点(编号 1∼n1), 右半部包含 n2 个点(编号 1∼n2), 二分图共包含 m 条边.

数据保证任意一条边的两个端点都不可能在同一部分中.

请你求出二分图的最大匹配数.

> 二分图的匹配: 给定一个二分图 G, 在 G 的一个子图 M 中, M 的边集 {E} 中的任意两条边都不依附于同一个顶点, 则称 M 是一个匹配.
> 
> 二分图的最大匹配: 所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配, 其边数即为最大匹配数.

下面是一些补充概念:

完美匹配: 如果一个图的某个匹配中, 所有的顶点都是匹配点, 那么它就是一个完美匹配.

交替路: 从一个未匹配点出发, 依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路.

增广路: 从一个未匹配点出发, 走交替路, 如果途径另一个未匹配点(出发的点不算), 则这条交替路称为增广路.

```c++
const int N = 510, M = 1e5+10;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];	//当前每个bottom匹配到的top
bool st[N];		//保证一个top考虑每个bottom只考虑一次
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool find(int x) {
	for (int i = h[x]; i != -1; i = ne[i]) {
		int j = e[i];
		if(!st[j]){	//如果还没有考虑过当前的bottom
			st[j] = true;
			//如果当前的bottom还没有被考虑或考虑这个bottom的top可以换一个人
			if (match[j] == 0 || find(match[j])) {
				match[j] = x;
				return true;
			}
		}
	}
	return false;
}
int main() {
	scanf("%d%d%d", &n1, &n2, &m);
	memset(h, -1, sizeof h);
	while (m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
	}
	int res = 0;	//最大匹配数
	//遍历每一个top来寻找bottom
	for (int i = 1; i <= n1; i++) {
		//清空所有的bottom,表示都还没有考虑
		memset(st, false, sizeof st);
		if (find(i)) res++;
	}
	printf("%d\n", res);
	return 0;
}
```

最后修改：2023 年 05 月 09 日

如果觉得我的文章对你有用，请随意赞赏

4 条评论

pmbaquvkfe
October 4th, 2024 at 09:07 pm

想想你的文章写的特别好https://www.ea55.com/

回复
gpytndjxyf
October 1st, 2024 at 08:42 pm

看的我热血沸腾啊https://www.237fa.com/

回复
sdyhowvxkf
September 23rd, 2024 at 08:59 am

看的我热血沸腾啊

回复
etbbwxvxyz
September 22nd, 2024 at 10:44 pm

叼茂SEO.bfbikes.com

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

贪心讲解
评论数： 6
搜索初步
评论数： 5
图论初步
评论数： 4
欢迎使用 Typecho
评论数： 2
比赛常用技巧及库函数
评论数： 2

dvlafvodtu
看的我热血沸腾啊www.jiwenlaw.com
usukxmmttv
不错不错，我喜欢看 www.jiwenlaw.com
dcyfmsthoa
想想你的文章写的特别好www.jiwenlaw.com
jbbnknwfgc
想想你的文章写的特别好https://www.ea55.com/
igbbiexfym
想想你的文章写的特别好https://www.ea55.com/

考研励志
评论数： 2
比赛常用技巧及库函数
评论数： 2
动态规划基础
评论数： 0
数据结构初步
评论数： 0
搜索初步
评论数： 5

图论初步

RearWaves • 2023 年 05 月 09 日

# 图论1

# 1 树和图的遍历: 拓扑排序

## 1.1 树和图的存储

有向图:$a\to b$

1. 邻接矩阵(适合稠密图),二维数组
2. 邻接表

无向图: 建两条边: $a\to b,\ b\to a$

**存储模板:**

```c++
const int N = 1e5 + 10;	//数据范围是10的5次方
const int M = 2 * N;	//以有向图的格式存储无向图, 所以每个节点至多对应2n-2条边

举例:现在$h[1]\to 3 \to 4 \to \varnothing \\h[2]\to 1 \to 4 \to \varnothing $ 要插入$1 \to 2$, 使用头插法, 变成$h[1]\to 2\to 3 \to 4 \to \varnothing $.

## 1.2 树与图的深度优先遍历

**遍历模板:**

### [846. 树的重心](https://www.acwing.com/problem/content/848/)

给定一颗树, 树中包含n个结点(编号1~n)和n-1条无向边.

请你找到树的重心, 并输出将重心删除后, 剩余各个连通块中点数的最大值.

重心定义: 重心是指树中的一个结点, 如果将这个点删除后, 剩余各个连通块中点数的最大值最小, 那么这个节点被称为树的重心.

> **分析:**dfs遍历每一个结点,求该节点删除之后剩余连通图的最大值,在求所有最大值中的最小值.

```c++
#include<bits/stdc++.h>
using namespace std;

## 1.3 树与图的广度优先遍历

### [847. 图中点的层次](https://www.acwing.com/problem/content/849/)

给定一个n个点m条边的有向图, 图中可能存在重边和自环. 所有边的长度都是1, 点的编号为1~n.

请你求出1号点到n号点的最短距离, 如果从1号点无法走到n号点, 输出-1.

输入格式: 两个整数n和m. 接下来m行, 一条从a走到b的长度为1的边.

输出格式: 输出1号点到n号点的最短距离.

## 1.4 拓扑排序

若一个由图中所有点构成的序列A满足: 对于图中的每条边(x, y), x在A中都出现在y之前, 则称A是该图的一个拓扑序列.

**模板:**

```c++
queue <- 所有入度为0的节点;
while (queue 不空) {
	t <- 队头;
	枚举t的所有出边 t-> j:
		删掉 t->j, d[j]--;
		if (d[j] == 0) {
			queue <- j;
		}
}
```

### [848. 有向图的拓扑序列](https://www.acwing.com/problem/content/850/)

给定一个n个点m条边的有向图, 点的编号是1到n, 图中可能存在重边和自环.

请输出任意一个该有向图的拓扑序列, 如果拓扑序列不存在, 则输出-1.

```c++
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int n, m;
int q[N], d[N];	//d表示各个点的入度

# 2 最短路

设一个图中的点有n个, 边有m条.

当$m$和$n^2$一个级别: 稠密图;

当$m$和$n$一个级别: 稀疏图.

![Hongda_2022-11-26_08-53-00](https://www.rearwaves.com/usr/assets/algorithm/graph/Hongda_2022-11-26_08-53-00.png)

## 2.1 朴素版的Dijkstra算法

![98504cdcddd6d683a91c09357395d12.png](https://www.rearwaves.com/usr/assets/algorithm/graph/0e5b3f689168da7c5c2eca6e3f065618.png)

### [849. Dijkstra求最短路 I](https://www.acwing.com/problem/content/851/)

## 2.2 堆优化的Dijkstra算法

### [850. Dijkstra求最短路 II](https://www.acwing.com/problem/content/852/)

## 2.3 bellman - ford算法

**1. 什么是bellman - ford算法:**

**2. 为什么需要back[a]数组:**

$$
1--(1)--> 2 --(1)--> 3\\|\_\_\_\_\_\_\_\_\_\_\_\_(3)\_\_\_\_\_\_\_\_\_\_\_\_\_|
$$

正确做法是用上轮节点2更新的距离--无穷大, 来更新节点3,  再取最小值, 所以节点3离起点的距离是3.

**3. 为什么是`dist[n]>0x3f3f3f3f/2`,  而不是`dist[n]>0x3f3f3f3f`:**

$$
5--(-2)-->n
$$

**模板:**

```c++
for n次
	for 所有边 a,b,w (松弛操作)
		dist[b] = min(dist[b],back[a] + w)
```

### [853. 有边数限制的最短路](https://www.acwing.com/problem/content/855/)

给定一个n个点m条边的有向图, 图中可能存在重边和自环,  **边权可能为负数**.

请你求出从1号点到n号点的最多经过k条边的最短距离, 如果无法从1号点走到n号点, 输出impossible.

注意: 图中可能 **存在负权回路** .

## 2.4 spfa算法

**1. 什么是spfa算法？**

**模板:**

```c++
for n次
	for 所有边 a,b,w (松弛操作)
		dist[b] = min(dist[b],back[a] + w)
```

**spfa 图解: **

给定一个有向图, 如下, 求A~E的最短路.

源点A首先入队, 然后A出队, 计算出到BC的距离会变短, 更新距离数组, BC没在队列中, BC入队

B出队, 计算出到D的距离变短, 更新距离数组, D没在队列中, D入队. 然后C出队, 无点可更新.

D出队, 计算出到E的距离变短, 更新距离数组, E没在队列中, E入队.

E出队, 此时队列为空, 源点到所有点的最短路已被找到, A->E的最短路即为8

### [851. spfa求最短路](https://www.acwing.com/problem/content/853/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环, **边权可能为负数**.

请你求出1号点到n号点的最短距离, 如果无法从1号点走到n号点, 则输出impossible .

数据保证**不存在负权回路**.

### [852. spfa判断负环](https://www.acwing.com/problem/content/854/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环,  **边权可能为负数**.

请你判断图中是否存在负权回路.

**解题思路:**

统计当前每个点的最短路中所包含的边数, 如果某点的最短路所包含的边数大于等于n, 则也说明存在环.

**维护cnt数组的作用:**
记录每个点到起点的边数, 当cnt[i] >= n 表示出现了边数>=结点数, 必然有环, 而且一定是负环！

## 2.5 Floyd算法

动态规划: `f[k][i][j]`代表(k的取值范围是从1到n), 在考虑了从1到k的节点作为中间经过的节点时, 从i到j的最短路径的长度.

`f[k][i][j]`可以从两种情况转移而来:

1. 从`f[k−1][i][j]`转移而来, 表示i到j的最短路径不经过k这个节点
2. 从`f[k−1][i][k]+f[k−1][k][j]`转移而来, 表示i到j的最短路径经过k这个节点

### [854. Floyd求最短路](https://www.acwing.com/problem/content/856/)

给定一个 n 个点 m 条边的有向图, 图中可能存在重边和自环, 边权可能为负数.

再给定 k 个询问, 每个询问包含两个整数 x 和 y, 表示查询从点 x 到点 y 的最短距离, 如果路径不存在, 则输出 `impossible`.

数据保证图中不存在负权回路.

# 3 最小生成树

![Hongda_2022-11-27_14-55-45](https://www.rearwaves.com/usr/assets/algorithm/graph/Hongda_2022-11-27_14-55-45.png)

## 3.1 普利姆算法(Prim)

**模板**

举例: 绿色的点为集合S, 下一个加入的点为F, 结果加上边C->F.

![5.png](https://www.rearwaves.com/usr/assets/algorithm/graph/64616_8a24258268-5.png)

### [858. Prim算法求最小生成树](https://www.acwing.com/problem/content/860/)

给定一个 n 个点 m 条边的无向图, 图中可能存在重边和自环, 边权可能为负数.

求最小生成树的树边权重之和, 如果最小生成树不存在则输出 `impossible`.

给定一张边带权的无向图 G=(V,E), 其中 V 表示图中点的集合, E 表示图中边的集合, n=|V|, m=|E|.

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树, 其中边的权值之和最小的生成树被称为无向图 G 的最小生成树.

## 3.2 克鲁斯卡尔算法(Kruskal)

**模板:**

```c++
1. 将所有边按权重从小到大排序
2. 枚举每条边 a,b, 权重是c
if a,b不连通 
	将这条边加入集合
```

### [859. Kruskal算法求最小生成树](https://www.acwing.com/problem/content/861/)

给定一个 n 个点 m 条边的无向图, 图中可能存在重边和自环, 边权可能为负数.

求最小生成树的树边权重之和, 如果最小生成树不存在则输出 `impossible`.

给定一张边带权的无向图 G=(V,E), 其中 V 表示图中点的集合, E 表示图中边的集合, n=|V|, m=|E|.

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树, 其中边的权值之和最小的生成树被称为无向图 G 的最小生成树.

```c++
const int N = 2e5 + 10;
int n, m;
int p[N];	//并查集
struct Edge {
	int a, b, w;
	//重载'<',按照权重排序
	bool operator< (const Edge& W)const {
		return w < W.w;
	}
}edges[N];

# 4 二分图

## 4.1 染色法

将所有点分成两个集合, 使得所有边只出现在集合之间, 就是二分图.

二分图: 一定不含有奇数环, 可能包含长度为偶数的环,  不一定是连通图.

### [860. 染色法判定二分图](https://www.acwing.com/problem/content/862/)

给定一个 n 个点 m 条边的无向图, 图中可能存在重边和自环.

请你判断这个图是否是二分图.

**方法一:dfs版本**

染色可以使用1和2区分不同颜色, 用0表示未染色.遍历所有点, 每次将未染色的点进行dfs, 默认染成1或者2.

由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return.染色失败相当于存在相邻的2个点染了相同的颜色.

**方法二:bfs版本**

颜色 1 和 2 表示不同颜色, 0 表示 未染色,定义queue是存PII, 表示 <点编号, 颜色>.

同理, 遍历所有点, 将未染色的点都进行bfs.队列初始化将第i个点入队, 默认颜色可以是1或2.

## 4.2 匈牙利算法

### [861. 二分图的最大匹配](https://www.acwing.com/problem/content/863/)

给定一个二分图, 其中左半部包含 n1 个点(编号 1∼n1), 右半部包含 n2 个点(编号 1∼n2), 二分图共包含 m 条边.

数据保证任意一条边的两个端点都不可能在同一部分中.

请你求出二分图的最大匹配数.

下面是一些补充概念:

完美匹配: 如果一个图的某个匹配中, 所有的顶点都是匹配点, 那么它就是一个完美匹配.

交替路: 从一个未匹配点出发, 依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路.

增广路: 从一个未匹配点出发, 走交替路, 如果途径另一个未匹配点(出发的点不算), 则这条交替路称为增广路.

4 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

图论初步

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款