【算法条记】图论根本（一）：建图、存图、树和图的遍历、拓扑排序、最小天生树

---

作甚图论

图的概念

图（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(V^2)               O(V2)的算法和                              O                      (                      E                      )                          O(E)               O(E)的算法的服从差异，在稠密图上二者服从相称，在希罕图上                              O                      (                      E                      )                          O(E)               O(E)的算法更优。
子图、天生子图

如果图a的节点集和边集分别是图b的节点集的子集和边集的子集，那么就称图a为图b的子图。
含有图G的全部极点的子图称为图G的天生子图
如果一个天生子图是树（无环连通图），那么就称这个天生子图为天生树
好比下面这张图，就是上面谁人出现很多次的无向图的一个天生树

同构

界说（图的同构）
给定两个图                               G                          G               G 和                               H                          H               H。若存在一个函数                               f                      :                      V                      (                      G                      )                      →                      V                      (                      H                      )                          f: V(G) \to V(H)               f:V(G)→V(H)满意对于恣意极点                               u                      ,                      v                          u, v               u,v，                              (                      u                      ,                      v                      )                      ∈                      E                      (                      G                      )                          (u, v) \in E(G)               (u,v)∈E(G) 当且仅当                               (                      f                      (                      u                      )                      ,                      f                      (                      v                      )                      )                      ∈                      E                      (                      H                      )                          (f(u), f(v)) \in E(H)               (f(u),f(v))∈E(H)， 则称                               f                          f               f 为从                               G                          G               G 到                               H                          H               H 的一个同构，而且称图                               G                          G               G 与                               H                          H               H 是同构的，记作                              G                      ≃                      H                          G \simeq H               G≃H
平凡的来讲，两个图同构就是布局雷同，好比下面两个图就是同构的

图的存储

算法角逐中，你想做图论的题，肯定得先学会怎么存图，图的存储告急分为以下几种方式：
直接存边

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

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

复制代码

必要遍历全部边、做给边排序（好比Kruskal算法）等使用的时间常用这种存图方法。
连接矩阵存边

连接矩阵就是用一个二维数组来存边，数组的下标就是边的端点，数组的值就是边的权值。
对于不带权的图，                              g                      [                      a                      ]                      [                      b                      ]                      =                      1                          g[a] = 1               g[a]=1表现存在从a到b的边，                              g                      [                      a                      ]                      [                      b                      ]                      =                      0                          g[a] = 0               g[a]=0表现不存在，这时的连接矩阵也叫可达性矩阵。

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

复制代码

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

1. int g[N][N];
3. while(m--){ // 输入m条边
4.     int a, b, w;
5.     cin >> a >> b >> w;
6.     g[a][b] = w;
7. }

复制代码

连接矩阵常用于稠密图，而且连接矩阵只能用于没有重边或重边可以忽略的环境（好比求最短路时，如果有重边就只要最短的一条就可以了，其他的都可以忽略）。
连接表存边

使用一个支持动态增长元素的数据布局构成的数组，如vector来存边。g[a]记载a的全部出边的信息（如尽头、边权等）。
对于不带权的图，g[a]存的是全部以a为出发点的边的尽头。

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

复制代码

对于带权图，g[a]存的是全部以a为出发点的边的尽头和边权。

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

复制代码

这是最常用的一种存边方法，存各种图都很恰当。
链式前向星存边

链式前向星存图着实就是用单链表实现的的连接表。
想用的话先去学链表，在这不做过多先容。

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

复制代码

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

复制代码

存各种图都很恰当，但不能快速查询一条边是否存在，也不能方便地对一个点的出边举行排序。
优点是边是带编号的，偶然会非常有效，而且如果 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）

和传统树的遍历一样，图的遍历也是一条路走到黑、不撞南墙不转头
给他一个遍历的出发点，他会先走该点的第一条出边，然后再遍历尽头的第一条出边…直到遍历到某个点没有出边了，再回溯去遍历第二条出边。

1. bool st[N];
3. void dfs(int u){
4.     st[u] = true;
5.     ...;
6.     for(int v : g[u]){
7.         if(st[v]) continue;
8.         dfs(v);
9.         ...;
10.     }
11.     ...;
12. }
14. dfs(1);

复制代码

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

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

1. bool st[N];
3. void bfs(int start){
4.     queue<int> q;
5.     q.push(start);
6.     st[start] = true;
7.     while(!q.empty()){
8.         int u = q.front();
9.         q.pop();
10.         ...;
11.         for(int v : g[u]){
12.                 if(st[v]) continue;
13.             q.push(v);
14.             st[v] = true;
15.             ...;
16.         }
17.     }
18. }
20. bfs(1);

复制代码

拓扑排序

什么是拓扑排序?

一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。
不绝举行上面的处置处罚，如果全部点都能被删掉，则这个图可以举行拓扑排序。
结论

一个图可以拓扑排序                               ⇔                          \Leftrightarrow               ⇔这个图是有向无环图（DAG）
例题

848. 有向图的拓扑序列

1. #include <iostream>
2. #include <algorithm>
3. #include <cstring>
4. #include <vector>
5. #include <queue>
6. #define endl '\n'
7. using namespace std;
8. const int N = 1e5 + 10;
9. int n, m;
10. vector<int> g[N]; // 邻接表存边
11. int d[N]; // 存每个点的入度
12. int res[N]; // 存拓扑序列（答案）
14. bool topsort(){
15.     int cnt = 0; // 记录当前删掉的节点数，也就是当前拓扑序列中的节点数
16.     queue<int> q;
17.     for(int i = 1; i <= n; i++){
18.         if(!d[i]) q.push(i); // 先把入度为0的点入队
19.     }
20.     while(!q.empty()){
21.         int t = q.front();
22.         q.pop();
23.         res[cnt++] = t; // 记录答案
24.         for(int i : g[t]){ // 遍历i的每条出边，给每个临点的入度-1（拿掉一条边）
25.             if(--d[i] == 0) q.push(i); // 将新的入度为0的点入队
26.         }
27.     }
28.     return cnt == n; // 如果每个点都能被删掉，就说明是有向无环图
29. }
31. int main(){
32.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
33.     cin >> n >> m;
34.     while(m--){
35.         int a, b;
36.         cin >> a >> b;
37.         g[a].push_back(b); // 边 a->b
38.         d[b]++; // b入度+1
39.     }
40.     if(!topsort()) cout << -1 << endl;
41.     else{
42.         for(int i = 0; i < n; i++) cout << res[i] << ' ';
43.     }
44.     cout << endl;
45.     return 0;
46. }

复制代码

一个本事

一个有向无环图的拓扑序列是有很多种的，如果按上面的写法，就是先把全部入度为0的节点删除，再去删除厥后继结点，但如果标题中要求优先输出编号大的或编号小的，把                              q                      u                      e                      u                      e                          queue               queue换成                              p                      r                      i                      o                      r                      i                      t                      y                      _                      q                      u                      e                      u                      e                          priority\_queue               priority_queue就好了,维护一个大根堆（编号大的先输出）/小根堆（编号小的先输出），其他代码都一样。
比方：确定角逐名次
最小天生树

起首，如果一个天生子图是树（无环连通图），那么就称这个天生子图为天生树
一个无向图有很多的天生树，规定边权和最小的一个叫做最小天生树。
求最小天生树有两种最简单常用的算法，Kruskal算法和Prim算法，两种算法都是基于贪心的头脑。
Kruskal求最小天生树

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

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

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

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

图示

例题

Kruskal算法求最小天生树

1. #include <iostream>
2. #include <algorithm>
3. #include <cstring>
4. #define endl \n'
5. using namespace std;
6. const int N = 2e5 + 10;
7. int n, m;
8. int fa[N];
10. struct Edge{
11.     int a, b, w; // 结构体数组存边
12. } edges[N];
14. bool cmp(Edge a,Edge b){
15.     return a.w < b.w; // 按边权从小到大排序
16. }
18. int find(int x){
19.     if(fa[x] != x)
20.         fa[x] = find(fa[x]);
21.     return fa[x];
22. }
24. int kruskal(){
25.     sort(edges, edges + m, cmp); // 按边权从小到大排序
26.     for(int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化
27.     int res = 0, cnt = 0; // res记录当前加到最小生成树中的边的权值的总和, cnt记录当前加了多少条边
28.     for(int i = 0; i < m; i++){
29.         int a = edges[i].a, b = edges[i].b, w = edges[i].w;
30.         a = find(a), b = find(b); // 并查集找祖先
31.         if(a != b){ // 如果a和b不在一个集合里，加边就不会成环
32.             fa[a] = b; // 加这条边
33.             res += w; // 将边权累加
34.             cnt++; // 又加进去一条边
35.         }
36.     }
37.     if(cnt < n - 1)
38.         return -1; // 加不到n - 1条边说明图不连通
39.     return res;
40. }
42. int main(){
43.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
44.     cin >> n >> m;
45.     for (int i = 0; i < m; i++){
46.         int a, b, w;
47.         cin >> a >> b >> w;
48.         edges[i] = {a, b, w}; // m条边
49.     }
50.     int t = kruskal();
51.     if(t == -1) cout << "impossible" << endl;
52.     else cout << t << endl;
53.     return 0;
54. }

复制代码

Prim求最小天生树

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

• 一开始，任取一个出发点到场连通部分（第一次迭代）
  
• 接下来每次迭代，遍历全部不在连通部分的点，找到离连通部分近来的点，将其到场连通部分
  
• 用该点到其他点的间隔更新其他点到连通部分的间隔
  
• 继续下一次迭代，直到全部点都加到最小天生树中（由于一次加一个点，以是n个点只需迭代n 次）
  
• 末了迭代n次后的连通部分就是该图的最小天生树。
  

图示

例题

Prim算法求最小天生树

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

复制代码

最大天生树

在求最小天生树的根本上，Kruskal就是把正序排序换成逆序排序，Prim就是把大于小于号变更一下，机动一点。