图论常见题目及算法

背景

近来都在刷 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 遍历,记录访问过的边