背景

近来都在刷 CCF 的题，准备认证考试。最近几天开始刷其中的第四题，一般而言，CCF 的第四题都是图论题。对于我这样之前没怎么刷题的人来说，图论题看上去就感觉很难，主要是感觉到很陌生，因为在实际的开发过程中比较少用到图这样的数据结构，都是线性的数据结构，连树都比较少用。

但是在刷得比较多的图论题后，发现其实图论题好像也就那么回事，也不是说简单，主要感觉来来去去都是考那几个东西，如果是没有接触过或者不会做的话，可能有点难，但是只要接触过相似的，直接套板子修改就行了（当然也有可能是我还接触的不够多 XD），另外，就是感觉没有什么题是 DFS/BFS 不能破，只是会不会超时，能拿多少的分的问题（对于 CCF 认证只想拿 300 分而言，有几十分就够了），其实很多算法的核心也就是 DFS 与 BFS。

所以在今晚刷完了 CCF 往年所有的第四题后，总结一下最近接触的图论问题及解法。

数据结构

首先，在解决问题之前，我们要先做好图论输入的模拟，图可以分为有向无向，有无权值。一般是以邻接矩阵或者邻接表的形式表示。

邻接矩阵 :graph = [[INF/False for _ in range(n+1)] for _ in range(n+1)] #带权值或无权图
邻接表：graph = [{}/[] for _ in range(n+1)] # 带权值或无权图

一般来说，邻接矩阵表示比较简单，但是时间空间成本都比较高，选用邻接表比较好，不过在 CCF 的认证似乎差别不大（样例水

问题及解法

最小生成树

问题：给一个无向带权图，选取其中一定数量的边生成一个包含所有点的树，且权值最小
方法：
- Prim 算法：优先队列 + BFS，每次弹出距生成树距离最小的未加入生成树的点
- Kruskal 算法：边排序 + 并查集
实例：
1. 最优灌溉
2. 数据中心

最短路径

对于一个图，指定两点间的最短距离，或者是指定一点的最长路径长度
方法：
- 迪杰斯特拉算法：优先队列。每次弹出到源点距离最小的点，并修改邻接的未确定点，记录确定情况
- spfa：队列。将源点入队列，每次弹出点后，修改邻接的点的距离，若修改且未入队则加入队列，记录入队列情况
- floyd 算法：求多源最短路径问题
  1 2 3 4
  for k in range(1,n+1): for i in range(1,n+1): for j in range(1,n+1): dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
变形：
- 最短路径中对特殊点有数量限制：spfa 中将数量记录放入队列开二维 dp 数组
- 大路小路问题（小路的权值为连续小路权值的平方）：floyd 算法生成新的小路边开两个 dp 数组进行 spfa

强连通分量

在有向图中，两个点互相可达称为强连通，任意两点均为强连通的子图称为强连通分量

方法：

Tarjar 算法：记录节点访问时间及最短时间，深度遍历邻接点并入栈，更新最短时间。当出现访问时间等于最短时间时，栈顶到该节点构成一个强连通分量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def tarjan(i):
    global ans,time
    time+=1
    DNF[i]=LOW[i]=time
    stack.append(i)
    instack[i]=True
    visited[i]=True
    for j in edges[i]:
        if not visited[j]:
            tarjan(j)
            LOW[i]=min(LOW[j],LOW[i])
        elif instack[j]:
            LOW[i]=min(LOW[j],LOW[i])
    if DNF[i]==LOW[i]:
        count=0
        while True:
            node = stack.pop()
            instack[node]=False

            count+=1
            if node==i:break

变形：
- 如果只是求强连通的点的对数，也可直接每一个点分别 BFS/DFS，确定单向可达性

树的直径

在树中，任意两个叶子节点的最长路径为树的直径
方法：当成图两次 BFS，第一次任一点开始，第二次由第一次结果开始
实例：
- 网络延时

欧拉路径

一个图如果能从一个点出发，每条边都经过一次后回到起始点，则这个图为欧拉图，这个遍历的路径为欧拉路径
方法：
1. 检查连通性：并查集 find union 检测是否每一个点都属于同一集合
2. 检查是否存在欧拉路径：每个点的度数均为偶数，或只有两个点度数为奇数且这两个点为起点终点
3. 确定存在欧拉路径后，直接 DFS 遍历，记录访问过的边

图论常见题目及算法

背景