【算法笔记】图论基础（一）：建图、存图、树和图的遍历、拓扑排序、最小生成树

---

何为图论

图的概念

图（Graph） 是一种数据结构，是由 节点（Node） 和 边（Edge） 组成的集合。

由节点所构成的集合就叫点集，由边所构成的集合就叫边集，点集和边集放在一起就形成了一张图。

注意：一张图的边集可以为空，但点集一定不能为空。

下面就是一个图，可以看到这个图有5个顶点，分别编号为{0，1，2，3，4}。同时这个图有5条边，例如，在顶点1和顶点3之间存在着一条边。

在图这个数据结构上面的所有问题和算法，统称为图论。

图的一些基本概念

有向图和无向图

图的边分为有向边和无向边，只有有向边的图就是有向图，只有无向边的图就是无向图。

上面的图片就是一个无向图，而如果把图改成这样，就是有向图。

如果对于边a -> b，a能到b、b不能到a，那这就是一条a到b的有向边。
如果对于边a – b，a能到b、b也能到a，那这就是一条a到b的无向边。

可以发现一个结论：无向边就是特殊的有向边、无向图就是特殊的有向图

解释：对于两个点a, b，你想在a、b之间连一条无向边，只需从a向b连一条有向边，再从b到a连一条有向边即可，就像下面这样：

所以我们研究的所有问题，只需考虑有向图即可，无向图只需在建图的时候建两条相反的有向边。

带权图

对于一个图，如果每一条边都被赋予一个数作为该边的权，这个图就是带权图。

边权其实也就是边长

比如下图

边权为正数的边就是正权边，比如上图中的(0, 1)、(2, 4)
边权为负数的边就是负权边，比如上图中的(1, 2)、(1, 3)

• 对于非带权图，表示的通常是节点和节点之间的连通关系
• 对于带权图，表示的同通常是节点和节点的距离

连通图和非连通图

对于无向图

对于无向图中的两个点u,v，如果存在一条从u到v的路径，则称为u和v连通。

连通图

非连通图

如果无向图的任意两个顶点均连通，这个图就是连通图，图的这一性质被称为连通性。

对于有向图

对于有向图中的两个点u,v，如果存在一条从u到v的路径，则称为u可达v。

若一张有向图的节点两两互相可达，则称这张图是强连通的
若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的

弱连通图

强连通图

度

顶点连接的边数叫做这个顶点的度

对于无向图

• 无向图中一个点的度数就是这个点的临边数。

比如下面的无向图，d(0) = 2, d(1) = 3, d(4) = 1…

对于有向图

有向图的度数分为两种：入度和出度

对于无向图中的一个点，

• 它的入度等于一这个点为终点的边（即直接指向这个点的边）的数量
• 它的出度等于以这个点为起点的边（即从这个点指向别的点的边）的数量

比如下面的有向图，din(0) = 0，dout(0) = 2, din(1) = 1, dout(1) = 2, din(4) = 1, dout(4) = 0…

一些结论

1.在任意无向图中，所有节点的度数和等于总边数*2。
2. 在任意无向图中，度为奇数的顶点的个数为偶数。
3. 在任意有向图中，所有节点入度的和等于所有节点出度的和。

环

图中起点和终点重合的非空路径叫做环

比如下面的图中，0 -> 1 -> 2 -> 0这条路径就是一个环

没有环的图叫无环图，没有环的有向图叫有向无环图，没有环的连通图称为树。

自环、重边、简单图、完全图

自环

对于图中的一条边(u, v)，如果u == v，那么这条边就被称做自环。

比如下图中的(2, 2)就是一个自环。

重边

如果图中有两条完全相同的边（起点、终点、方向都相同），那么他们就被称为一组重边。

比如下图中，(2, 4)和(2, 4)就是一组重边，但(0, 1) 和（1, 0）不是。

简单图

没有重边和自环的图被称作简单图。

任意两个节点都相邻的无向简单图被称为完全图。

若有向图满足任意不同两点间都有两条方向不同的边，则称为有向完全图。

稀疏图和稠密图

• 若一张图的边数远小于其点数的平方，那么它是一张 稀疏图 。
• 若一张图的边数接近其点数的平方，那么它是一张 稠密图 。

稀疏图和稠密图一般来讨论时间复杂度为$O(V^2)$的算法和$O(E)$的算法的效率差异，在稠密图上二者效率相当，在稀疏图上$O(E)$的算法更优。

子图、生成子图

如果图a的节点集和边集分别是图b的节点集的子集和边集的子集，那么就称图a为图b的子图。

含有图G的所有顶点的子图称为图G的生成子图

如果一个生成子图是树（无环连通图），那么就称这个生成子图为生成树

比如下面这张图，就是上面那个出现很多次的无向图的一个生成树

同构

定义（图的同构）

给定两个图 $G$ 和 $H$。若存在一个函数 $f:V(G)\to V(H)$满足对于任意顶点 $u,v$，$(u,v)\in E(G)$ 当且仅当 $(f(u),f(v))\in E(H)$， 则称 $f$ 为从 $G$ 到 $H$ 的一个同构，并且称图 $G$ 与 $H$ 是同构的，记作$G\simeq H$

通俗的来讲，两个图同构就是结构相同，比如下面两个图就是同构的

图的存储

算法竞赛中，你想做图论的题，肯定得先学会怎么存图，图的存储主要分为以下几种方式：

直接存边

最简单粗暴的一种，用一个结构体数组直接存边

struct Edge{int a, b, w; // 表示一条 a->b 的边，边权为w
}edges[N];for(int i = 0; i < m; i++){ // 输入m条边int a, b, w;cin >> a >> b >> w;edges[i] = {a, b, w};
}

需要遍历所有边、做给边排序（比如Kruskal算法）等操作的时候常用这种存图方法。

邻接矩阵存边

邻接矩阵就是用一个二维数组来存边，数组的下标就是边的端点，数组的值就是边的权值。

对于不带权的图，$g[a][b]=1$表示存在从a到b的边，$g[a][b]=0$表示不存在，这时的邻接矩阵也叫可达性矩阵。

int g[N][N];while(m--){ // 输入m条边int a, b;cin >> a >> b;g[a][b] = 1;
}

对于带权图，$g[a][b]=w$表示存在从a到b、权值为w的边，$g[a][b]=0$表示不存在边

int g[N][N];while(m--){ // 输入m条边int a, b, w;cin >> a >> b >> w;g[a][b] = w;
}

邻接矩阵常用于稠密图，并且邻接矩阵只能用于没有重边或重边可以忽略的情况（比如求最短路时，如果有重边就只要最短的一条就可以了，其他的都可以忽略）。

邻接表存边

使用一个支持动态增加元素的数据结构构成的数组，如vector来存边。g[a]记录a的所有出边的信息（如终点、边权等）。

对于不带权的图，g[a]存的是所有以a为起点的边的终点。

vector<int> g[N];for(int i = 0; i < m; i++){int a, b;cin >> a >> b;g[a].push_back(b);
}for(int v : g[u]){ // 遍历u的所有出边，v就是出边的终点}

对于带权图，g[a]存的是所有以a为起点的边的终点和边权。

typedef pair<int, int> PII;
vector<PII> g[N];for(int i = 0; i < m; i++){int a, b, w;cin >> a >> b >> w;g[a].push_back({b, w});
}for(auto i : g[u]){ // 遍历u的所有出边int v = i.first, w = i.second; // v:出边的终点，w:边权 
}

这是最常用的一种存边方法，存各种图都很适合。

链式前向星存边

链式前向星存图其实就是用单链表实现的的邻接表。

想用的话先去学链表，在这不做过多介绍。

int h[N], e[N], ne[N], idx;void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx++; // add(a, b) : 加一条 a->b的边
}memset(h, -1, sizeof h); // 表头初始化成-1
idx = 0;for(int i = h[t]; i != -1; i = ne[i]){ // 遍历t的出边int j = e[i]; // j是出边的终点
}

int h[N], e[N], ne[N], w[N], idx;void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; // add(a, b, c) : 加一条 a->b 边权为c的边
}memset(h, -1, sizeof h); // 表头初始化成-1
idx = 0;for(int i = h[t]; i != -1; i = ne[i]){ // 遍历t的出边int j = e[i]; // j是出边的终点
}

存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。

优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1即是 i 的反边

图的遍历

树和图的遍历（图示）

树

dfs遍历顺序：1， 2， 5， 9， (5)， 10， (5)， (2)， (1)， 3， 6， 11，(6)， (3)， 7， (3)， (1)， 4， 8

bfs遍历顺序：1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11

图

dfs遍历顺序：1， 2， 5， 7， 6，（7），（5），（2），（1）， 3， （1）， 4

bfs遍历顺序：1， 2， 3， 4， 5， 6， 7

树和图的深度优先遍历（dfs）

和传统树的遍历一样，图的遍历也是一条路走到黑、不撞南墙不回头

给他一个遍历的起点，他会先走该点的第一条出边，然后再遍历终点的第一条出边…直到遍历到某个点没有出边了，再回溯去遍历第二条出边。

bool st[N];void dfs(int u){st[u] = true;...;for(int v : g[u]){if(st[v]) continue;dfs(v);...;}...;
}dfs(1);

树和图的广度优先遍历（bfs）

给他一个遍历的起点，他会把这个点所有的出边都走完，然后再去走所有第一步到的终点的所有出边…直到队首的点没有出边可走（队列为空，所有点就都遍历完了）

bool st[N];void bfs(int start){queue<int> q;q.push(start);st[start] = true;while(!q.empty()){int u = q.front();q.pop();...;for(int v : g[u]){if(st[v]) continue;q.push(v);st[v] = true;...;}}
}bfs(1);

拓扑排序

什么是拓扑排序?

一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。

一直进行上面的处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。

结论

一个图可以拓扑排序 $\iff$这个图是有向无环图（DAG）

例题

848. 有向图的拓扑序列

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int n, m;
vector<int> g[N]; // 邻接表存边
int d[N]; // 存每个点的入度
int res[N]; // 存拓扑序列（答案）bool topsort(){int cnt = 0; // 记录当前删掉的节点数，也就是当前拓扑序列中的节点数queue<int> q;for(int i = 1; i <= n; i++){if(!d[i]) q.push(i); // 先把入度为0的点入队}while(!q.empty()){int t = q.front();q.pop();res[cnt++] = t; // 记录答案for(int i : g[t]){ // 遍历i的每条出边，给每个临点的入度-1（拿掉一条边）if(--d[i] == 0) q.push(i); // 将新的入度为0的点入队}}return cnt == n; // 如果每个点都能被删掉，就说明是有向无环图
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;while(m--){int a, b;cin >> a >> b;g[a].push_back(b); // 边 a->bd[b]++; // b入度+1}if(!topsort()) cout << -1 << endl;else{for(int i = 0; i < n; i++) cout << res[i] << ' ';}cout << endl;return 0;
}

一个技巧

一个有向无环图的拓扑序列是有很多种的，如果按上面的写法，就是先把所有入度为0的节点删除，再去删除其后继结点，但如果题目中要求优先输出编号大的或编号小的，把$queue$换成$priority\_queue$就好了,维护一个大根堆（编号大的先输出）/小根堆（编号小的先输出），其他代码都一样。

例如：确定比赛名次

最小生成树

首先，如果一个生成子图是树（无环连通图），那么就称这个生成子图为生成树
一个无向图有很多的生成树，规定边权和最小的一个叫做最小生成树。

求最小生成树有两种最简单常用的算法，Kruskal算法和Prim算法，两种算法都是基于贪心的思想。

Kruskal求最小生成树

Kruskal算法非常好理解，简单粗暴，他是一个向图中加边的过程。

算法过程

1. 将所有的边都拿掉，只留下所有的点，并将边按边权从小到大排序。
2. 从小到大遍历每条边，看加上这条边会不会形成环，如果这个边与之前选择的所有边不会组成环，就选择这条边，将边权加到答案，反之，舍去。
3. 遍历完所有边后，筛选出来的边和所有的顶点构成此图的最小生成树。

判断是否会产生回路的方法为：使用并查集。

• 在初始状态下给各个顶点在不同的集合中。
• 遍历过程的每条边，判断这两个顶点的是否在一个集合中
• 如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，再加边就会成环，这条边不要。如果不在一个集合中，则要这条边。

图示

例题

Kruskal算法求最小生成树

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl \n'
using namespace std;
const int N = 2e5 + 10;
int n, m;
int fa[N];struct Edge{int a, b, w; // 结构体数组存边
} edges[N];bool cmp(Edge a,Edge b){return a.w < b.w; // 按边权从小到大排序
}int find(int x){if(fa[x] != x)fa[x] = find(fa[x]);return fa[x];
}int kruskal(){sort(edges, edges + m, cmp); // 按边权从小到大排序for(int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化int res = 0, cnt = 0; // res记录当前加到最小生成树中的边的权值的总和, cnt记录当前加了多少条边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不在一个集合里，加边就不会成环fa[a] = b; // 加这条边res += w; // 将边权累加cnt++; // 又加进去一条边}}if(cnt < n - 1)return -1; // 加不到n - 1条边说明图不连通return res;
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;for (int i = 0; i < m; i++){int a, b, w;cin >> a >> b >> w;edges[i] = {a, b, w}; // m条边}int t = kruskal();if(t == -1) cout << "impossible" << endl;else cout << t << endl;return 0;
}

Prim求最小生成树

Prim算法是向图中加点的过程，他是维护了两个集合：{已经加到最小生成树中的点和边}（连通部分） 和 {还未加到最小生成树中的点和边}，每次将离连通部分的最近的点和点对应的边加入连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小，最后的连通部分就是该图的最小生成树。

算法过程

1. 一开始，任取一个起点加入连通部分（第一次迭代）
2. 接下来每次迭代，遍历所有不在连通部分的点，找到离连通部分最近的点，将其加入连通部分
3. 用该点到其他点的距离更新其他点到连通部分的距离
4. 继续下一次迭代，直到所有点都加到最小生成树中（由于一次加一个点，所以n个点只需迭代n 次）
5. 最后迭代n次后的连通部分就是该图的最小生成树。

图示

例题

Prim算法求最小生成树

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 505;
int n, m;
int g[N][N]; // 邻接矩阵存图
int dist[N]; // dist[i]表示当前i距离连通部分的距离
bool st[N]; // st标记当前点是否已经加入连通部分，st[i] = true说明已经加入了，st[i] = false说明还没加入int prim(){memset(dist, 0x3f, sizeof dist); // 一开始，连通部分没有点，所有点到连通部分的距离为正无穷int res = 0; // res记录当前加到最小生成树中的边的权值的总和for(int i = 0; i < n; i++){ // 迭代n次int t = -1; // t来记录未加入连通部分的点中距离连通部分最近的点for(int j = 1; j <= n; j++){ // 遍历所有不在连通部分的点, 找到离连通部分最近的点if(!st[j] && (t == -1 || dist[t] > dist[j])) // t == -1 : 防止越界; dist[t] > dist[j]：点j比点t距离连通部分近t = j; // 把t换成j}if(i && dist[t] == 0x3f3f3f3f) // 如果连通部分有点，离连通部分最近的点dist还是正无穷，说明图不连通return 0x3f3f3f3f;if(i)res += dist[t]; // 从第二个加入连通部分的点开始，把其距离连通部分的距离加到答案（也就是将其对应的边加入连通部分）st[t] = 1; // 标记一下这个点加进去了for(int j = 1; j <= n; j++)dist[j] = min(dist[j], g[t][j]); // 遍历所有点，用t到其他点的距离更新其他点到连通部分的距离}return res;
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;memset(g, 0x3f, sizeof g); // 由于要取min，所以初始化成正无穷while(m--){int a, b, w;cin >> a >> b >> w;g[a][b] = g[b][a] = min(g[a][b], w); // 求最小生成树，如果有重边就只要最短边}int t = prim();if(t == 0x3f3f3f3f) cout << "impossible" << endl;else cout << t << endl;return 0;
}

最大生成树

在求最小生成树的基础上，Kruskal就是把正序排序换成逆序排序，Prim就是把大于小于号调换一下，灵活一点。