Decade
Graph Algorithm
Zhongjun Qiu 元婴开发者
  2023-01-05 21:16:44   2025-04-29 23:06:32    9.7k Words  43 Mins  

图论的常见算法与应用，涵盖图的存储结构、图的遍历、拓扑排序、最小生成树（Kruskal 和 Prim）、最短路径算法（Floyd、Dijkstra、Bellman-Ford、SPFA、Johnson）等。还涉及分层图、差分约束、二分图、欧拉图及树相关算法，如 LCA、树的直径、重构树和树链剖分等。

存储结构

  • 邻接矩阵

无脑存

1
2
3
4
int[][] g = new int[n][m];
for (int i = 0;i < n;i++)
for (int j = 0;j < m;j++)
  ...
  • 邻接表
1
2
3
4
5
List<Integer>[] g = new List[; //List<int[]>[] g;可以存边权等附加信息。
for (int i = 0;i < n; i++) g[i] = new ArrayList<>(); //千万别忘
for (int i = 0;i < n;i++){
 for (int v : g[i]) ...
}
  • 链式前向星
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class E{
    // 边的终点 下一条边在edge中的编号 边的权值
    int to, ne, wt;
    E(int t, int n, int w){to = t;ne = n;wt = w;}
    E(int t, int n){to = t;ne = n;}
}
E[] edge = new E[m]; //如果是无向图 new E[m*2]要开两倍
int[] hd = new int[n]; //hd[i]：顶点i为起点的第一条边
void add(int u, int v, int idx){
    edge[idx] = new E(v, hd[v]);// 存边u->v
    hd[u] = idx;
}
for (int i = hd[v];i != 0;i = edge[i].ne){
int u = edge[i].to;
...
}

图的遍历

  • 没啥好说的 与树遍历差别在于图遍历需要 visited[]数组 考虑到图可能不连通，需要对每一个点进行扫描
1
2
3
for (int i = 0;i < n;i++){
    if (!vis[i]) DFS(i) //或BFS(i)
}

DFS

1
2
3
4
5
6
7
8
void dfs(int u) {
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].x) {
        if (!vis[e[i].t]) {
            dfs(v);
        }
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(int u) {
    Q.push(u);
    vis[u] = 1;
    while (!Q.empty()) {
        u = Q.front();Q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            if (!vis[e[i].to]) {
                Q.push(e[i].to);
                vis[e[i].to] = 1;
            }
        }
    }
}

拓扑排序

前提：有向无环图（DAG）

核心：维护入度为 0 的顶点集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
List<Integer>[] g = new List[N];
int[] indeg = new int[N]; //入度
List<Integerres; //拓扑排序结果
for (int i = 0;i < m;i++){
    int u, v;
    indeg[v]++;
    g[u].add(v);
}
Deque<Integerq = new LinkedList<>();
for (int i = 1;i <= n;i++) if (indeg[i] == 0) q.offerLast(i);
while (!q.isEmpty()){
    int u = q.pollFirst();
    res.add(u);
    for (int v : g[u]){
        if (--indeg[v] == 0) q.offerLast(v);
    }
}
if (res.size() == n) // DAG 可以拓扑排序
else // 无法拓扑排序
  • 求字典序最大/最小的拓扑排序 将算法中的队列替换成最大堆/最小堆实现的优先队列即可,此时总的时间复杂度为 O(E + Vlog V) 。

最小生成树

Kruskal（优先使用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int kruskal(int n, int[][] edges){
    //用堆代替边集数组排序
    PriorityQueue<int[]g = new PriorityQueue<>((o1, o2) -o1[2] - o2[2]);
    Collections.addAll(g, edges);
    int ans = 0, cnt = 0;
    while (cnt != n-1){
        int[] e = g.poll();
        int v = find(e[0]), u = find(e[1]);
        if ( v != u ){
            union(u, v);
            ans += e[2];
            cnt++;
        }
    }
    return ans; //最小总权值
}
// ...省略并查集操作
  • O(mlog m)

Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int primHeap(int n, int[][] edges) {
    int res = 0;
    //邻接表存图（适用边较少，稀疏图） <顶点v,[]{顶点u, 距离}>
    List<List<int[]>g = new ArrayList<>();
    for (int i = 0;i < n;i++) g.add(new ArrayList<>());
    for (int[] e : edges){
        g.get(e[0]).add(new int[]{e[1], e[2]});
        g.get(e[1]).add(new int[]{e[0], e[2]});
    }
    int[] vis = new int[n];
    PriorityQueue<int[]q = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
    q.offer(new int[]{0,0}); //从第0个节点开始构造
    while (n 0){
        int[] cur = q.poll();
        if (vis[cur[0]] == 1) continue;
        vis[cur[0]] = 1;
        res += cur[1];
        --n;
        for (int[] p : g.get(cur[0])){
            q.offer(new int[]{p[0], p[1]});
        }
    }
    return res;
}
  • O((m + n)log n)

最短路

  • 性质 对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

    对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

    对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数  <  = n，边数  <  = n − 1。

Floyd

求任意两个结点之间的最短路的。

适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（==不能有个负环==）

1
2
3
4
5
6
7
for (k = 1; k <= n; k++) {
    for (x = 1; x <= n; x++) {
        for (y = 1; y <= n; y++) {
                f[x][y] = min(f[x][y], f[x][k] + f[k][y]); //每次以k为中转点（动态规划）
        }
    }
}

f[x][k]+f[k][y]==可能会爆 int==。

Dijkstra

对于边 (u, v) ，松弛操作对应下面的式子： dis (v) = min (dis (v), dis (u) + w(u, v)) 。

非负权图 上单源最短路径的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] dijkstra (int n, int k){
  int[] vis = new int[n+1], dis = new int[n+1];
  Arrays.fill(dis,0x3f3f3f3f);
  dis[k] = 0; //k为源点
  for (int t = 1;t <= n;t++){
      int minidx = -1;
      for (int i = 1;i <= n;i++){
          if (vis[i]==0 && (minidx==-1||dis[i]<dis[minidx])) minidx = i;
      }
      vis[minidx] = 1;
      for (int[] e : g[minidx]){
          int v = e[0], w = e[1];
          dis[v] = Math.min(dis[v], dis[minidx]+w);
      }
  }
  return dis;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int[] dijkstraHeap (int n, int k){
  int[] dis = new int[n+1], vis = new int[n+1];
  Arrays.fill(dis,0x3f3f3f3f);
  dis[k] = 0;
  PriorityQueue<int[]q = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
  q.offer(new int[]{k, 0});
  while (!q.isEmpty()){
      int u = q.poll()[0];
      //可能有一个点被松弛两次的情况 后弹出的距离肯定比先弹出的小，所以直接跳过
      if (vis[u] == 1) continue;
      vis[u] = 1;
      for (int[] e : g[u]){
          int v = e[0], w = e[1];
          if (dis[v] dis[u]+w){
              dis[v] = dis[u]+w;
              q.offer(new int[]{v, dis[v]});
          }
      }
  }
  return dis;
}

时间复杂度

  • 暴力：O(n2 + m) = O(n2)

  • 优先队列：O(mlog m) 在稀疏图中，m = O(n)，优先队列；

    在稠密图中，m = O(n2)，暴力。

Bellman-Ford

Bellman-Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。 在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少+1 ，而最短路的边数最多为n − 1 ，因此整个算法最多执行n − 1 轮松弛操作。故总时间复杂度为O(mn) 。 但还有一种情况，如果从S 点出发，抵达一个负环时，松弛操作会无休止地进行下去。因此如果第 n轮循环时仍然存在能松弛的边，说明从 S点出发，能够抵达一个负环。

需要注意的是，以 点为源点跑 Bellman-Ford 算法时，如果没有给出存在负环的结果，只能说明从 S点出发不能抵达一个负环，而不能说明图上不存在负环。 因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman-Ford 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int[] bellman(int n, int k){
    int[] dis = new int[n+1];
    Arrays.fill(dis, 0x3f3f3f3f)
    dis[k] = 0;
    for (int t = 1 ; t <= n-1;t++){
        int flag = 1;// 如果此次循环没有边更新 说明松弛提前结束
        //对每条边进行遍历更新
        for (int[] e : g){
            int u = e[0], v = e[1], w = e[2];
            if (dis[v] dis[u]+w) {
                dis[v] = dis[u]+w;
                flag = 0;
            }
        }
        if (flag == 1) break;
    }
    boolean exist = true;//判断是否有负环
    for (int[] e : g){
        int u = e[0], v = e[1], w = e[2];
        if (dis[v] dis[u]+w) {
            exist = false;break;
        }
    }
    return exist ? dis:new int[]{};
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] spfa(int n, int k) {
	boolean exist = true;
	int[] cnt = new int[n+1];//用于判断负环(一个节点至多加入队列n-1次 反之存在负环)
//vis判断该节点是否在队列中（访问过后出队列 vis[i]=0）
//跟其他算法不同（其他算法大都表示有没有访问过该元素）
    for (int i = 1;i <= n;i++) h[i] = INF;
    Deque<Integerq = new LinkedList<>();
    q.offerLast(k);cnt[k]++;vis[k] = 1;h[k] = 0;
    while (!q.isEmpty() && !exist){
        int v = q.pollFirst();vis[v] = 0;
        for (int i = hd[v];i != 0;i = edge[i].ne){
            int u = edge[i].to, w = edge[i].wt;
            if (h[u] < h[v]+w){
                h[u] = h[v]+w;
                if (vis[u] == 1) continue;
                q.offerLast(u);cnt[u]++;vis[u]=1;
                if (cnt[u]==n+1) exist = true;
            }
        }
    }
	return exist?dis:new int[]{};
}

Johnson 全源最短路径

我们新建一个虚拟节点（在这里我们就设它的编号为 0 ）。从这个点向其他所有点连一条边权为 0 的边。 接下来用 Bellman-Ford(SPFA) 算法求出从 0 号点到其他所有点的最短路，记为 hi 。 假如存在一条从 u 点到 v 点，边权为 w 的边，则我们将该边的边权重新设置为 w + hu − hv 。 接下来以每个点为起点，跑 n 轮 Dijkstra 算法即可求出任意两点间的最短路了。 一开始的 Bellman-Ford 算法并不是时间上的瓶颈，若使用 priority_queue 实现 Dijkstra 算法， 该算法的时间复杂度是 O(nmlog m) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Main{
    static int n, m, N = 5010, M = 9010, INF = 0x3f3f3f3f;
    static E[] edge = new E[M];// 链式前向星存图
    static int[] hd = new int[N], vis = new int[N];
    static int[] dis = new int[N],h = new int[N];
    public static void main(String[] args) throws IOException {
        for (int i = 1;i <= m;i++) add(i, u, v, w);
        for (int i = 1;i <= n;i++) add(m+i, 0, i, 0); //超级源点0 到其他点距离都为0
        int tp = SPFA(0); //此时图里一共有n+1个点 要松弛n次（不是n-1）
        if (tp == -1){
            System.out.println(-1); return; //有负环 寄
        }
        for (int i= 1;i <= n;i++)
        for (int k = hd[i];k !=0;k = edge[k].ne)
            edge[k].wt += h[i]-h[edge[k].to]; //w+h[u]-h[v] 更新权值
        for (int i = 1;i <= n;i++){
            dijkstra(i);// 每个点跑一遍最短路
            for (int k = 1;k <= n;k++){
                if (dis[k] == INF) System.out.println(INF);
                //把之前加的权值减去就是实际最短路长度
                else System.out.println(dis[k]-h[i]+h[k]);
            }
        }
    }
    private static void dijkstra(int k) {...}
    private static int SPFA(int k) {...}
}

0-1 最短路

0-1BFS 用来解决：边权值为 0 或 1，或者能够转化为这种边权值的最短路问题，时间复杂度 O( NM )。

主要操作：用 deque，从 0 边扩展到的点 push 到队首，反之则到队尾。 ==不需要 vis[]数组==

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] dis = new int[n*m];
Arrays.fill(dis, 1 << 30);
Deque<int[]pq = new LinkedList<>();
pq.add(new int[]{0, 0}); dis[0] = 0;
while (!pq.isEmpty()){
    int[] cur = pq.pollFirst();
    int u = cur[0];
    for (int v : g[u]){
        int p = grid[x][y], nd = dis[u]+p;
        if (nd < dis[v]){
            dis[v] = nd;
            if (p == 0) pq.offerFirst(new int[]{nd, v}); //边为0 加入队首
            else pq.offerLast(new int[]{nd, v}); //边为1 加入队尾
        }
    }
}

不同方法的比较

Bellman-Ford 最短路算法 Floyd Dijkstra Johnson
单源最短路 最短路类型 每对结点间的最短路 单源最短路 每对结点间的最短路
任意图 作用于 任意图 非负权图 任意图
能 能否检测负环？ 能 不能 能
中/小 作用图的大小 小 大/中 大/中
O(NM) 时间复杂度 O(N3) O((M + N)log M) O(NMlog M)

注：表中的 Dijkstra 算法在计算复杂度时均用 priority_queue 实现。

分层图最短路

分层图最短路，如：有 k 次零代价通过一条路径，求总的最小花费。对于这种题目，我们可以采 用 DP 相关的思想，设 disi, j 表示当前从起点 i 号结点，使用了 j 次免费通行权限后的最短路径。 显然，dis 数组可以这么转移:

disi, j = min {min {disfrom, j − 1}, min {disfrom, j + w}}

其中， from 表示 i 的父亲节点， w 表示当前所走的边的边权。当 j − 1 ≥ k 时， disfrom, j = ∞ 。 事实上，这个 DP 就相当于把每个结点拆分成了 k + 1 个结点，每个新结点代表使用不同多次免费 通行后到达的原图结点。换句话说，就是每个结点 ui 表示使用 i 次免费通行权限后到达 u 结点。

P4568 [JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static int test, N = 10010, M = (int)1e9+7;
static int n, m, k;
static List<int[]>[] g = new List[N];
static int[][] dis = new int[N][11], vis = new int[N][11];
static void solve() throws Exception {
    n = ni(); m = ni(); k = ni();
    int s = ni(), t = ni();
    for (int i = 0;i < n;i++){
        g[i] = new ArrayList<>();
        Arrays.fill(dis[i], M);
    }
    for (int i = 1;i <= m;i++){
        int u = ni(), v = ni(), w = ni();
        g[u].add(new int[]{v, w});
        g[v].add(new int[]{u, w});
    }
    PriorityQueue<int[]pq = new PriorityQueue<>((x, y)->
        x[2]==y[2] ? x[1]-y[1] : x[2]-y[2]
    );
    pq.add(new int[]{s, 0, 0}); dis[s][0] = 0;
    while (!pq.isEmpty()){
        int[] cur = pq.poll();
        int u = cur[0], c = cur[1], d = cur[2];
        if (vis[u][c] == 1) continue;
        vis[u][c] = 1;
        for (int[] ne : g[u]){
            int v = ne[0], w = ne[1];
            if (dis[v][c] d+w){
                dis[v][c] = d+w;
                pq.add(new int[]{v, c, dis[v][c]});
            }
            if (c+1 <= k && dis[v][c+1] d){
                dis[v][c+1] = d;
                pq.add(new int[]{v, c+1, dis[v][c+1]});
            }
        }
    }
    int ans = M;
    for (int i = 0;i <= k;i++) ans = min(ans, dis[t][i]);
    pw.println(ans);
}

差分约束（不等式）

差分约束系统 是一种特殊的 n 元一次不等式组，它包含 n 个变量 x1, x2, …, xn 以及 m 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 xi − xj ≤ ck ，其中1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m 并且 ck 是常数（可以是非负数，也可以是负数）。

我们要解决的问题是: 求解 x1 = a1, x2 = a2, …, xn = an ，使得所有约束条件得到满足，否则无解。

差分约束系统中的每个约束条件 xi − xj ≤ ck 都可以变形成 xi ≤ xj + ck ，这与单源最短路中 的三角形不等式 dist [y] ≤ dist [x] + z 非常相似。因此，我们可以把每个变量 xi 看做图中的一 个结点，对于每个约束条件 xi − xj ≤ ck ，从结点 j 向结点 i 连一条长度为 ck 的有向边。

注意到，如果 {a1, a2, …, an} 是该差分约束系统的一组解，那么对于任意的常数 d ， {a1 + d, a2 + d, …, an + d} 显然也是该差分约束系统的一组解，因为这样做差后 d 刚好被消掉。

设 dist [0] = 0 并向每一个点连一条权重为 0 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解；否则， xi = dist [i] 为该差分约束系统的一组解。即建立超级源点0后跑 SPFA.

  • 判断是否有解

    小 K 的农场

    题目大意: 求解差分约束系统，有 m 条约束条件，每条都为形如 xa − xb ≥ ck ， xa − xb ≤ ck 或 xa = xb 的形式，判断该差分约束系统有没有解。

    题意 转化 连边
    xa − xb ≥ ck xb − xa ≤ −c add(a, b, -c);
    xa − xb ≤ ck xa − xb ≤ ck add(b, a, c);
    xa = xb xa − xb ≤ 0, xb − xa ≤ 0 add(b, a, 0), add(a, b, 0);

  • 求最值解 差分约束问题可以转化为最短路或最长路问题，所以两种转化也就形成了两种不同的连边方法。

  1. 连边后求最短路 将 xj − xi ≤ k 形式不动，即从 i 到 j 连一条边权为 k 的边。==加入超级源点后求最短路，得到 xi ≤ 0 所有 x 最大解==。
  2. 连边后求最长路 将 xj − xi ≤ k 变形为 xi − xj ≥ −k ，即从 j 到 i 连一条边权为 −k 的边。==加入超级源点后求最长 路，得到 xi ≥ 0 所有 x 最小解==。

  • 最长路 最长路问题即为在给定的图中，计算从源点到所有顶点的最长路。保证图中没有正环。

    其中一种实现方法为若 du + w > dv，则将 dv 更新为 du + w（实际上就是把最短路中的大于号改成小于号），并在初始化时将 dis数组全部初始化为一个极小值（−INF），其余部分和用 SPFA 求最短路一样。

    分糖果

二分图

  • 定义 节点由两个集合组成，且两个集合内部没有边的图。

  • 性质 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。

    二分图不存在长度为奇数的环

  • 二分图判断 染色法：首先将任意的一个顶点染成红色，再把这个点相邻的顶点染成蓝色，如果按照这种染色方式可以将所有的顶点全部着色，并且相邻的顶点的颜色不同，那么该图就是一个二分图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static boolean solve() {
    for (int i = 1;i <= n;i++){// 可能图不连通 要对每个点都判断一遍
        if (color[i] == 0) {
            if (!dfs(i, 1)) return false;
        }
    }
    return true;
}
static boolean dfs(int v, int c){ // 0-未染色 1-白色 -1-黑色
    color[v] = c;
    for (int u : g[v]){
    if (color[u] == c) return false;
    if (color[u] == 0 && !dfs(u, -c)) return false;
    }
    return true;
}
  • 二分图最大匹配 求一个二分图中最大匹配的边数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static int[] match = new int[N]; //match[u] = v 表示右集合中u点匹配的是左集合中的v点
static int[] vis = new int[N];
public static void main(String[] args) throws Exception{
    // 对左集合中每个点进行匹配
    for (int i = 1;i <= n;i++) {
        Arrays.fill(vis, 0); //每一次寻找中 每个点只能访问一次
        if (find(i)) ++ans;
    }
    System.out.println(ans);
}
private static boolean find(int u) {
    for (int v : g[u]) {
    if (vis[v]==1) continue;
        vis[v] = 1;
        // 右集合中的点v没有匹配 || v匹配的左集合中的点match[v]可以再找到一个新的匹配
            // 就可以让v成为u的匹配
        if (match[v]==0 || find(match[v])) {
        match[v] = u;
        return true;
        }
    }
    return false;
}

  • 最小路径覆盖 定义：通俗点将，就是在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。

    最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。

    最小不相交路径覆盖：每一条路径经过的顶点各不相同。如图，其最小路径覆盖数为 3。即 1->3>4，2，5。

    最小可相交路径覆盖：每一条路径经过的顶点可以相同。如果其最小路径覆盖数为 2。即 1->3->4，2->3>5。

    特别的，每个点自己也可以称为是路径覆盖，只不过路径的长度是 0。

König 定理: 一个二分图中的最大匹配数等于这个图中的最小点覆盖数

最小路径覆盖数 = 图中节点数 - 最小点覆盖数

（如果是最小可相交路径覆盖，只要求出原图的传递闭包，再新建一个图进行计算即可）

2549. 估计人数 - AcWing 题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
static int[][] a = new int[22][22];
static int[] v = new int[210], match = new int[210];
static boolean[][] g = new boolean[210][210];
// 二分图求最大匹配
static boolean find(int u){
    for (int i = 1;i <= cnt;i++){
        if (!g[u][i] || v[i]==1) continue;
        v[i] = 1;
        if (match[i]==0 || find(match[i])){
            match[i] = u;
            return true;
        }
    }return false;
}
static void solve() throws IOException{
    io = in.readLine().split(" ");
    n = ni(io[0]); m = ni(io[1]);
    for (int i = 0;i < n;i++){
        char[] c = in.readLine().toCharArray();
        for (int j = 0;j < m;j++){
            if (c[j] == '1') a[i][j] = ++cnt;
        }
    }
    // 按题目意思建图（无向图邻接矩阵）
    for (int i = 0;i < n;i++){
        for (int j = 0;j < m;j++){
            if (a[i][j]*a[i][j+1] != 0) g[a[i][j]][a[i][j+1]] = true;
            if (a[i][j]*a[i+1][j] != 0) g[a[i][j]][a[i+1][j]] = true;
        }
    }
    // 这题求可相交，所以先跑以便Floyd求传递闭包。
    for (int i = 1;i <= cnt;i++){
        for (int j = 1;j <= cnt;j++){
            for (int k = 1;k <= cnt;k++){
                g[i][j] |= g[i][k] & g[k][j];
            }
        }
    }
    // 求最大匹配
    for (int i = 1;i <= cnt;i++){
        Arrays.fill(v, 0);
        if (find(i)) res++;
    }
    // 最小路径覆盖 = 节点数量 - 最小点覆盖
    out.println(cnt-res);
}

欧拉图

  1. 定义
  • 欧拉回路：通过图中每条边恰好一次的回路
  • 欧拉通路：通过图中每条边恰好一次的通路
  • 欧拉图：具有欧拉回路的图
  • 半欧拉图：具有欧拉通路但不具有欧拉回路的图
  1. 判断

无向图是欧拉图当且仅当：

  • 非零度顶点是连通的
  • 顶点的度数都是偶数 无向图是半欧拉图当且仅当：
  • 非零度顶点是连通的
  • 恰有 2 个奇度顶点 有向图是欧拉图当且仅当：
  • 非零度顶点是强连通的
  • 每个顶点的入度和出度相等 有向图是半欧拉图当且仅当：
  • 非零度顶点是弱连通的
  • 仅有一个顶点的出度与入度之差为 1
  • 仅有一个顶点的出度与入度之差为 -1
  • 其他顶点的入度和出度相等
  1. 求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static int n, m, idx;
static int[] deg = new int[501], ans = new int[5001];
static Deque<Integer>[] g = new Deque[501];
static void dfs(int u){
    Deque<Integercur = g[u];
    while (!cur.isEmpty()){
        int v = cur.pollFirst();
        g[v].remove(u);
        dfs(v);
    }
    // 存路径
    ans[idx++] = u;
}
static void solve() throws IOException{
    m = ni();
    for (int i = 1;i <= 500;i++) g[i] = new LinkedList<>();
    for (int i = 1;i <= m;i++){
        int u = ni(), v = ni();
        // 无向图直接++；有向图起点--，终点++
        deg[u]++; deg[v]++;
        g[u].offerFirst(v); g[v].offerFirst(u);
        n = max(n, max(u, v));
    }
    int start = 1;
    for (int i = n;i >= 1;i--){
        // 如果有奇数度，则为半欧拉图，dfs起点必须从奇数度的那个节点开始
        // 如果是有向图，dfs起点必须从度为-1的那个节点开始
        if (deg[i]%2==1) start = i;
        // 求字典序最小/最大的欧拉路，需要对边按题目要求进行排序
        Collections.sort((List<Integer>)g[i]);
    }
    dfs(start);
    // 路径倒着遍历
    for (int i = idx-1;i >= 0;i--) out.println(ans[i]);
}

树相关

LCA

LCA（Least Common Ancestors），是指在有根树中，找出某两个结点 u 和 v 最近的公共祖先。

  • 核心：倍增 首先我们要记录各个点的深度和他们2j级的的祖先，用数组deep[i]表示每个节点的深度，f[i][j]表示节点i的2j级祖先。（例如上图 17 的 1 级祖先是 14， 2 级是 10， 4 级是 3， 以此来推）

    fa[u][i] = fa[fa[u][i-1]][i-1]：f[i][j] 就是i的2j级祖先，那f[i][j − 1]就是i的2j − 1 级祖先。 又因为 2j − 1 + 2j − 1 = 2j，所以i的 2j − 1 级祖先的2j − 1级祖先 就是i的2j 级祖先。

1
2
3
4
5
6
7
8
static void dfs(int u, int f) { //u当前节点 f为父节点 搜索从根节点开始即dfs(root, 0)
    deep[u] = deep[f]+1;
    fa[u][0] = f; //u的2^0级祖先 即 u的1级祖先是其父节点
    for (int i = 1;(1 << i) <= deep[u];i++){
    	fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (int v : g[u]) if (v != f) dfs(v, u); //父节点不再访问
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int LCA(int u, int v) {
    if (deep[u] deep[v]) {int tp = v;v = u;u = tp;} //让v的深度始终是大于u的
    int dis = deep[v]-deep[u]; //深度差
    //将u的深度变得与v相同
    for (int i = 0;(1<<i) <= dis;i++){
        //快速加的意思 任意正整数都可以表示为几个2的幂次的和
        if (((dis>>i) & 1) == 1) v = fa[v][i];
    }
    if (u == v) return u;
    for (int i = 19;i >= 0;i--){
        if (fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

例如求解上图中 LCA(13,18)：

  • 让 13 和 18 的深度相同（变成小的那个），所以 13 不变 18 变成 12， 此时深度都为 6.

  • 13 和 12 第23级祖先(也就是深度比他们少 8 的，6-8=-2<0 相当于根节点)都为 1。相同，继续往下。

  • 13和12 第22级祖先(深度少4，为6-4=2)都为2。相同，继续往下。

  • 13和12 第21级祖先(深度少2，为6-2=4)分别是7和5。不同，都往上爬2个高度变成7和5。

  • 7和5 第20级祖先(深度少2，为4-1=3)都是3。此时循环到了最后一次，说明3就是LCA。

  • 返回f[7][0]或者f[5][0],结果都是 3。所以13 和 18 的 LCA 是 3

用欧拉序列转化为 RMQ 问题

定义

对一棵树进行 DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，可以得 到一个长度为 2n − 1 的序列，这个序列被称作这棵树的欧拉序列。

在下文中，把结点 u 在欧拉序列中第一次出现的位置编号记为 pos (u) （也称作节点 u 的欧拉 序)，把欧拉序列本身记作 E[1...2n − 1] 。

过程

有了欧拉序列， LCA 问题可以在线性时间内转化为 RMQ 问题，即 pos (LCA(u, v)) = min {pos (k) ∣ k ∈ E[pos (u)..pos (v)]} 。

这个等式不难理解: 从 u 走到 v 的过程中一定会经过 LCA(u, v) ，但不会经过 LCA(u, v) 的祖先。 因此，从 u 走到 v 的过程中经过的欧拉序最小的结点就是 LCA(u, v) 。

用 DFS 计算欧拉序列的时间复杂度是 O(n) ，且欧拉序列的长度也是 O(n) ，所以 LCA 问题可以在 O(n) 的时间内转化成等规模的 RMQ 问题。

树的直径

树上任意两节点之间最长的简单路径即为树的「直径」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static int n, m, ans;
static List<Integer>[] g;
static int[] d1, d2; // d1[i]存储节点i到叶子节点的最大距离 d2[i]存储节点i到叶子节点的第二大距离
static void solve() throws Exception{
    dfs(1, 0);
    out.println(ans);
}
static void dfs(int u, int f){
    d1[u] = d2[u] = 0;
    for (int v : g[u]){
        if (v == f) continue;
        dfs(v, u);
        int t = d1[v]+1;
        if (t d1[u]){
            d2[u] = d1[u]; d1[u] = t;
        }else if (t d2[u]){
            d2[u] = t;
        }
    }
    ans = max(ans, d1[u]+d2[u]);
}

Kruskal 重构树

设 fi 为 i 所在联通块的根。 算法流程和 Kruskal 最小生成树的过程非常类似:

  1. 将所有边按边权从小到大排序
  2. 顺序遍历每条边 (u, v, w) ，若 u, v 已经联通跳过，否则建立一个新点 x ，让 x 作为 fu 与 fv 的父亲（即连 x ⇒ fu 和 时间复杂度 O(mlog m + nlog n) 。 最后，以最后一个建立的新点作为 rt ，就是一颗重构树了（下面是一个无向图联通变成重构树的例子，排序后第 i 条边的编 号是 n + i ，点权是红色，蓝色是新点，黑色是原来的点）。

这棵树有如下性质：

  • 原树若有 n 个节点，那么新树有 2n − 1 个节点，根是 2n − 1 。因为建的新点就是合并两个点的次数，合并 n − 1 次。最 后一次合并作为根，凑成了整个树。

  • 所有原来的点就是叶子节点。因为建新图过程中我们没有让原来的点当父亲。

  • 对于任意的 x 点， 它的祖先链从下往上点权都是非严格递增的。因为每次合并的时候，只有  ≤ w 的边都构造好了，所以此时 fu 的点权也  ≤ w。 因此重构树的点权是一个大根堆。跟上一个性质的等价的。

  • 对于一个 x 和一个值 v 。从 x 出发只经过  ≤ v 的边能到达的点集  = x 的祖先节点中深度最小的点权  ≤ v 的点 z 的子树中的 原来的点集。（证明：这颗子树外的点显然不行，因为再往上点权  > v ，说明再往上其他的点使通过  > v 的边才和 x 点连上 的，所以不行；这颗子树内的点显然可以，因为这是一个大根堆，所以子树内的点都可以用  ≤ v 的边互相可达，他们在新树 上的路径，经过的所有编号就是原树上经过的所有边。

  • 对于任意 x, y ，其最小瓶颈边权 (使其最大边最小的路径的最大边) 为 x, y 在新树上的 LCA 点权。 x, y 在经过 LCA 这条边 后恰好联通，由于从小到大顺序执行，说明这条边是路径上最大的边。 如果求最大生成树，反着排序，那么偏序关系都反转，就不赘述了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0;i < m;i++){
    int u = ni(), v = ni(), w = ni();
    e[i][0] = u; e[i][1] = v; e[i][2] = w;
}Arrays.sort(e, 0, m, (x, y)->y[2]-x[2]);
int cur = n;
for (int i = 0;i < m;i++){
    int u = e[i][0], v= e[i][1], w = e[i][2];
    int x = find(u), y = find(v);
    if (x != y){
        ++cur;
        fa[x] = fa[y] = cur;
        g[cur].add(x); g[cur].add(y);
        val[cur] = w;
    }
}

树上差分

树上差分有什么作用？举个例子，如果题目要求对树上的一段路径进行操作，并询问某个点或某条边被经过的次数，树上差分就可以派上用场了。这就是树上差分的基本操作。 树上差分，就是利用差分的性质，对路径上的重要节点进行修改（而不是暴力全改），作为其差分数组的值，最后在求值时，利用 dfs 遍历求出差分数组的前缀和，就可以达到降低复杂度的目的。

点差分

设将两点 u,v 之间路径上的所有点权增加 x，o=LCA(u,v),o 的父亲节点为 p，则操作如下：

1
diff[u]+=x,diff[v]+=x,diff[o]-=x,diff[p]-=x;

这样，只要 dfs 一遍，遍历时统计以每个节点为根的树的节点的权值和，就是当前节点的最终权值！ 是不是很厉害

就是差分的思想，这里就不多说了。 边差分

思想一样，讲一下操作。

设将两点 u,v 之间路径上的所有边权增加 x，o=LCA(u,v)，以每条边两端深度较大的节点存储该边的差分数组，则操作如下：

1
diff[u]+=x,diff[v]+=x,diff[o]-=2*x;

同样地，只要 dfs 一遍，遍历时统计以每个节点为根的树的节点的权值和，就是当前节点到父亲节点的边的最终权值了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void cal(int u, int fa) throws Exception{
    dep[u] = dep[fa]+1;
    f[u][0] = fa;
    for (int i = 1;(1<<i) <= dep[u];i++) f[u][i] = f[f[u][i-1]][i-1];
    for (int[] t : g[u]){
        int v = t[0], idx = t[1];
        if (v == fa) continue;
        cal(v, u);
        e[v] = idx; //以深度更大的点代表这条边
    }
}
for (int i = 1;i < n;i++){
    int u = ni(), v = ni();
    //建图把边的编号记录下来
    g[u].add(new int[]{v, i});
    g[v].add(new int[]{u, i});
}

树链剖分

先来回顾两个问题：

  1. 将树从 x 到 y 结点最短路径上所有节点的值都加上 z

    这也是个模板题了吧

    我们很容易想到，树上差分可以以 O(n+m)的优秀复杂度解决这个问题

  2. 求树从 x 到 y 结点最短路径上所有节点的值之和

    lca 大水题，我们又很容易地想到，dfs O(n)预处理每个节点的 dis（即到根节点的最短路径长度）

    然后对于每个询问，求出 x,y 两点的 lca，利用 lca 的性质 distance (x,y)=dis(x)+dis(y)-2*dis(lca) 求出结果

    时间复杂度 O(mlogn+n)

现在来思考一个 bug：

如果刚才的两个问题结合起来，成为一道题的两种操作呢？

刚才的方法显然就不够优秀了（每次询问之前要跑 dfs 更新 dis）

树剖是通过轻重边剖分将树分割成多条链，然后利用数据结构来维护这些链（本质上是一种优化暴力）

首先明确概念：

  • 重儿子：父亲节点的所有儿子中子树结点数目最多（size 最大）的结点；
  • 轻儿子：父亲节点中除了重儿子以外的儿子；
  • 重边：父亲结点和重儿子连成的边；
  • 轻边：父亲节点和轻儿子连成的边；
  • 重链：由多条重边连接而成的路径；
  • 轻链：由多条轻边连接而成的路径；

比如上面这幅图中，用黑线连接的结点都是重结点，其余均是轻结点，

2-11 就是重链，2-5 就是轻链，用红点标记的就是该结点所在重链的起点，也就是下文提到的 top 结点，

还有每条边的值其实是进行 dfs 时的执行序号。

变量声明：

1
2
3
4
5
6
static int n, m, root, time = 0;
static long[] f = new long[N<<2], lazy = new long[N<<2];
static int[] siz = new int[N], dep = new int[N], son = new int[N];
static int[] dfn = new int[N], top = new int[N], faz = new int[N];
static long[] w = new long[N], rk = new long[N];
static List<Integer>[] g = new List[N];

time 时间戳

root 根节点

f[u] 保存结点 u 的父亲节点

d[u] 保存结点 u 的深度值

size[u] 保存以 u 为根的子树节点个数

son[u] 保存重儿子

top[u] 保存当前节点所在链的顶端节点

dfn[u] 保存树中每个节点剖分以后的新编号（DFS 序）

rk[u] 保存当前 dfs 标号在树中所对应的节点的权值

树链剖分的实现

1，对于一个点我们首先求出它所在的子树大小,找到它的重儿子（即处理出 size,son 数组），

解释:比如说点 1，它有三个儿子 2，3，4

2 所在子树的大小是 5

3 所在子树的大小是 2

4 所在子树的大小是 6

那么 1 的重儿子是 4

ps:如果一个点的多个儿子所在子树大小相等且最大

那随便找一个当做它的重儿子就好了

叶节点没有重儿子，非叶节点有且只有一个重儿子

2，在 dfs 过程中顺便记录其父亲以及深度（即处理出 f,d 数组），操作 1,2 可以通过一遍 dfs 完成

dfs 跑完大概是这样的，大家可以手动模拟一下

3，第二遍 dfs，然后连接重链，同时标记每一个节点的 dfs 序，并且为了用数据结构来维护重链，我们在 dfs 时保证一条重链上各个节点 dfs 序连续（即处理出数组 top,dfn,rk）

dfs 跑完大概是这样的，大家可以手动模拟一下

4，两遍 dfs 就是树链剖分的主要处理，通过 dfs 我们已经保证一条重链上各个节点 dfs 序连续，那么可以想到，我们可以通过数据结构（以线段树为例）来维护一条重链的信息

回顾上文的那个题目，修改和查询操作原理是类似的，以查询操作为例，其实就是个 LCA，不过这里使用了 top 来进行加速，因为 top 可以直接跳转到该重链的起始结点，轻链没有起始结点之说，他们的 top 就是自己。需要注意的是，每次循环只能跳一次，并且让结点深的那个来跳到 top 的位置，避免两个一起跳从而插肩而过。

1
2
3
4
5
6
7
while (top[u] != top[v]){
    if (dep[top[u]] < dep[top[v]]) {int tp = u;u = v;v = tp;}
    upd(1, 1, n, dfn[top[u]], dfn[u], val);
    u = faz[top[u]];
}
if (dep[u] dep[v]) {int tp = u;u = v;v = tp;}
upd(1, 1, n, dfn[u], dfn[v], val);

5，树链剖分的时间复杂度

树链剖分的两个性质：

1，如果(u,v)是一条轻边，那么 size(v)<size(u)/2；

2，从根结点到任意结点的路所经过的轻重链的个数必定都小于 logn；

可以证明，树链剖分的时间复杂度为

P3384 【模板】重链剖分/树链剖分 - 洛谷 | 计算机科学教育新生态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
public class Main {
    static String ss, io[];
    static int test, N = 100010, M = 1000000007;
    static int n, m, root, time = 0;
    static long[] f = new long[N<<2], lazy = new long[N<<2];
    static int[] siz = new int[N], dep = new int[N], son = new int[N];
    static int[] dfn = new int[N], top = new int[N], faz = new int[N];
    static long[] w = new long[N], rk = new long[N];
    static List<Integer>[] g = new List[N];
    //===================================线段树==============================================
    static void up(int k){
        f[k] = f[k*2]+f[k*2+1]; f[k] %= M;
    }
    static void down(int k, int l, int m, int r){
        if (lazy[k] == 0) return;
        f[k*2] += lazy[k]*(m-l+1); f[k*2] %= M;
        f[k*2+1] += lazy[k]*(r-m); f[k*2+1] %= M;
        lazy[k*2] += lazy[k]; lazy[k*2] %= M;
        lazy[k*2+1] += lazy[k]; lazy[k*2+1] %= M;
        lazy[k] = 0;
    }
    static void build(int k, int l, int r){
        if (l == r){
            f[k] = rk[l]%M;
            return;
        }
        int mid = l+r >1;
        build(k*2, l, mid);
        build(k*2+1, mid+1, r);
        up(k);
    }
    static void upd(int k, int l, int r, int s, int t, long val){
        if (s <= l && r <= t){
            f[k] += (r-l+1)*val; f[k] %= M;
            lazy[k] += val; lazy[k] %= M;
            return;
        }
        int mid = l+r >1;
        down(k, l, mid, r);
        if (s <= mid) upd(k*2, l, mid, s, t, val);
        if (t mid) upd(k*2+1, mid+1, r, s, t, val);
        up(k);
    }
    static long qry(int k, int l, int r, int s, int t){
        if (s <= l && r <= t) return f[k];
        int mid = l+r >1;
        long res = 0;
        down(k, l, mid, r);
        if (s <= mid) res = (res+qry(k*2, l, mid, s, t))%M;
        if (t mid) res = (res+qry(k*2+1, mid+1, r, s, t))%M;
        up(k);
        return res;
    }
    static void dfs(int u, int fa, int depth){
        dep[u] = depth; faz[u] = fa;
        siz[u] = 1; son[u] = 0;
        for (int v : g[u]){
            if (v == fa) continue;
            dfs(v, u, depth+1);
            siz[u] += siz[v];
            if (siz[v] siz[son[u]]) son[u] = v;
        }
    }
    static void dfs1(int u, int topf){
        dfn[u] = ++time; rk[time] = w[u];
        top[u] = topf;
        if (son[u] == 0) return;
        dfs1(son[u], topf);
        for (int v : g[u]){
            if (v == faz[u] || v == son[u]) continue;
            dfs1(v, v);
        }
    }
    //================================查询和更新任意两个节点==================================
    static void upd2(int u, int v, long val){
        while (top[u] != top[v]){
            if (dep[top[u]] < dep[top[v]]) {int tp = u;u = v;v = tp;}
            upd(1, 1, n, dfn[top[u]], dfn[u], val);
            u = faz[top[u]];
        }
        if (dep[u] dep[v]) {int tp = u;u = v;v = tp;}
        upd(1, 1, n, dfn[u], dfn[v], val);
    }
    static void qry2(int u, int v){
        long res = 0;
        while (top[u] != top[v]){
            if (dep[top[u]] < dep[top[v]]) {int tp = u;u = v;v = tp;}
            res = (res+qry(1, 1, n, dfn[top[u]], dfn[u]))%M;
            u = faz[top[u]];
        }
        if (dep[u] dep[v]) {int tp = u;u = v;v = tp;}
        res = (res+qry(1, 1, n, dfn[u], dfn[v]))%M;
        out.println(res);
    }
    //================================查询和更新一个子树==================================
    //此时不涉及树链剖分，跑一遍dfs序，建立线段树即可。
    static void upd1(int u, long val){
        upd(1, 1, n, dfn[u], dfn[u]+siz[u]-1, val);
    }
    static void qry1(int u){
        out.println(qry(1, 1, n, dfn[u], dfn[u]+siz[u]-1));
    }
    static void solve() throws Exception{
        n = ni(); m = ni(); root = ni(); M = ni();
        for (int i = 1;i <= n;i++){
            g[i] = new ArrayList<>();
            w[i] = ni();
        }
        for (int i = 2;i <= n;i++){
            int u = ni(), v = ni();
            g[u].add(v); g[v].add(u);
        }
        dfs(root, 0, 1);
        dfs1(root, root);
        build(1, 1, n);
        for (int i = 1;i <= m;i++){
            int op = ni();
            if (op == 1) upd2(ni(), ni(), nl()%M);
            else if (op == 2) qry2(ni(), ni());
            else if (op == 3) upd1(ni(), nl()%M);
            else qry1(ni());
        }
    }
}
Graph Algorithm
2023/01/05/Graph-Algorithm/
Author
Zhongjun Qiu
Published
2023-01-05 21:16
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 存储结构
  2. 图的遍历
  3. 拓扑排序
  4. 最小生成树
    1. Kruskal（优先使用）
    2. Prim
  5. 最短路
    1. Floyd
    2. Dijkstra
    3. Bellman-Ford
    4. SPFA
    5. Johnson 全源最短路径
    6. 0-1 最短路
    7. 不同方法的比较
    8. 分层图最短路
  6. 差分约束（不等式）
  7. 二分图
  8. 欧拉图
  9. 树相关
    1. LCA
    2. 树的直径
    3. Kruskal 重构树
    4. 树上差分
    5. 树链剖分
  1. 存储结构
  2. 图的遍历
  3. 拓扑排序
  4. 最小生成树
    1. Kruskal（优先使用）
    2. Prim
  5. 最短路
    1. Floyd
    2. Dijkstra
    3. Bellman-Ford
    4. SPFA
    5. Johnson 全源最短路径
    6. 0-1 最短路
    7. 不同方法的比较
    8. 分层图最短路
  6. 差分约束（不等式）
  7. 二分图
  8. 欧拉图
  9. 树相关
    1. LCA
    2. 树的直径
    3. Kruskal 重构树
    4. 树上差分
    5. 树链剖分