发表更新基础 / 模板17 分钟读完 (大约2511个字)

图论

本文内容参考《算法》，《算法导论》，OI Wiki。

拓扑排序

例题

实现

  • 时间复杂度为 \(O(n+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
28
29
30
31
32
33
34
private static int[] topologicalSort(int n, int[][] edges) {
    int[] in = new int[n];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1];
        g[u].add(v);
        in[v]++;
    }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
        }
    }

    int idx = 0;
    int[] res = new int[n];
    while (!q.isEmpty()) {
        int x = q.poll();
        res[idx++] = x;
        for (int y : g[x]) {
            if (--in[y] == 0) {
                q.offer(y);
            }
        }
    }

    // 拓扑排序不存在
    assert idx == n;

    return res;
}

最小生成树

例题

Prim

实现一：朴素版本

  • 时间复杂度为 \(O(n^{2})\)。
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
private static int prim(int n, int[][] edges) {
    int[][] g = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(g[i], Integer.MAX_VALUE);
        g[i][i] = 0;
    }
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (g[u][v] > w) {
            g[u][v] = g[v][u] = w;
        }
    }

    int[] d = new int[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    boolean[] vis = new boolean[n];

    int res = 0;
    d[0] = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (t == -1 || d[t] > d[j])) {
                t = j;
            }
        }

        // 不是连通图，最小生成树不存在
        assert d[t] != Integer.MAX_VALUE;

        vis[t] = true;
        res += d[t];

        for (int j = 0; j < n; j++) {
            d[j] = Math.min(d[j], g[t][j]);
        }
    }

    return res;
}

实现二：优先队列优化

  • 时间复杂度为 \(O(m\log{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
28
29
30
31
32
33
34
35
36
37
private static int prim(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u].add(new int[]{v, w});
        g[v].add(new int[]{u, w});
    }

    int[] d = new int[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    boolean[] vis = new boolean[n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    int res = 0, cnt = 0;
    d[0] = 0;
    q.offer(new int[]{0, 0});
    while (!q.isEmpty()) {
        int u = q.poll()[0];
        if (vis[u]) continue;
        vis[u] = true;
        res += d[u];
        if (++cnt == n) break;
        for (int[] t : g[u]) {
            int v = t[0], w = t[1];
            if (!vis[v] && d[v] > w) {
                d[v] = w;
                q.offer(new int[]{v, d[v]});
            }
        }
    }

    // 不是连通图，最小生成树不存在
    assert cnt == n;

    return res;
}

Kruskal

  • 时间复杂度为 \(O(m\log{m})\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);

    int cnt = 1, res = 0;
    UnionFind uf = new UnionFind(n);
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (uf.connected(u, v)) continue;
        uf.union(u, v);
        res += w;
        if (++cnt == n) break;
    }

    // 不是连通图，最小生成树不存在
    assert cnt == n;

    return res;
}

最短路

例题

Dijkstra

  • 使用场景：解决边权非负的单源最短路问题。

实现一：朴素版本

  • 时间复杂度为 \(O(n^{2})\)。
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
private static final int INF = (int) 1e9;

private static int dijkstra(int n, int[][] edges) {
    int[][] g = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(g[i], INF);
        g[i][i] = 0;
    }
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u][v] = Math.min(g[u][v], w);
    }

    int[] d = new int[n];
    Arrays.fill(d, INF);
    boolean[] vis = new boolean[n];

    d[0] = 0;
    while (true) {
        int t = -1;
        for (int i = 0; i < n; i++) {
            if (!vis[i] && (t == -1 || d[t] > d[i])) {
                t = i;
            }
        }

        if (t == n - 1 || d[t] == INF) {
            break;
        }
        vis[t] = true;

        for (int i = 0; i < n; i++) {
            d[i] = Math.min(d[i], d[t] + g[t][i]);
        }
    }

    return d[n - 1] == INF ? -1 : d[n - 1];
}

实现二：优先队列优化

  • 时间复杂度为 \(O(m\log{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
28
29
30
31
32
33
private static final int INF = (int) 1e9;

private static int dijkstra(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u].add(new int[]{v, w});
    }

    int[] d = new int[n];
    Arrays.fill(d, INF);
    boolean[] vis = new boolean[n];
    Queue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    d[0] = 0;
    q.offer(new int[]{0, 0});
    while (!q.isEmpty()) {
        int u = q.poll()[0];
        if (u == n - 1) break;
        if (vis[u]) continue;
        vis[u] = true;
        for (int[] t : g[u]) {
            int v = t[0], w = t[1];
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.offer(new int[]{v, d[v]});
            }
        }
    }

    return d[n - 1] == INF ? -1 : d[n - 1];
}

Bellman-Ford

  • 时间复杂度为 \(O(nm)\)。
  • 使用场景：解决任意边权的单源最短路问题；判断是否存在负环；解决有边数限制的单源最短路问题。

实现一：朴素版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static final int INF = (int) 1e9;

private static int bellmanFord(int n, int[][] edges) {
    int[] d = new int[n];
    Arrays.fill(d, INF);

    d[0] = 0;
    for (int i = 0; i < n; i++) {
        for (var e : edges) {
            int u = e[0], v = e[1], w = e[2];
            d[v] = Math.min(d[v], d[u] + w);
        }
    }

    // d[n - 1] == INF 时，最短路不存在
    return d[n - 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
36
private static final int INF = (int) 1e9;

private static int spfa(int n, int[][] edges) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        g[u].add(new int[]{v, w});
    }

    int[] d = new int[n];
    Arrays.fill(d, INF);
    Queue<Integer> q = new ArrayDeque<>();
    boolean[] on = new boolean[n];

    d[0] = 0;
    q.offer(0);
    on[0] = true;
    while (!q.isEmpty()) {
        int u = q.poll();
        on[u] = false;
        for (int[] t : g[u]) {
            int v = t[0], w = t[1];
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (!on[v]) {
                    q.offer(v);
                    on[v] = true;
                }
            }
        }
    }

    // d[n - 1] == INF 时，最短路不存在
    return d[n - 1];
}

Floyd-Warshall

  • 时间复杂度为 \(O(n^{3})\)。
  • 使用场景：解决任意边权的多源最短路问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static final int INF = (int) 1e9;

private static int[][] floyd(int n, int[][] edges) {
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dp[i], INF);
        dp[i][i] = 0;
    }
    for (var e : edges) {
        int u = e[0], v = e[1], w = e[2];
        dp[u][v] = Math.min(dp[u][v], w);
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][k] != INF && dp[k][j] != INF) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
    return dp;
}

最近公共祖先

例题

倍增

  • 预处理时间复杂度为 \(O(n\log{n})\)，查询时间复杂度为 \(O(\log{n})\)。
  • 原理：\(f[i][j]\) 表示节点 \(j\) 的第 \(2^{i}\) 个祖先，当利用倍增得到 \(f\) 时，对于任意两个节点 \(x,y\)，先将较深的节点向上跳到相同深度，然后两个节点贪心的向上跳到 \(\operatorname{lca}\) 下方距离它最近的节点，最后得到的节点就是 \(\operatorname{lca}\) 的直接子节点。（在进行倍增时，根节点的父节点可以是任何值，因为该值不会影响算法的正确性）
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
private static void dfs(int x, int fa, List<Integer>[] g, int[][] f, int[] d) {
    f[0][x] = fa;
    for (int i = 1; 1 << i <= d[x]; i++) {
        f[i][x] = f[i - 1][f[i - 1][x]];
    }
    for (int y : g[x]) {
        if (y != fa) {
            d[y] = d[x] + 1;
            dfs(y, x, g, f, d);
        }
    }
}

private static int lca(int x, int y, int[][] f, int[] d) {
    if (d[x] > d[y]) {
        int t = x; x = y; y = t;
    }

    int diff = d[y] - d[x];
    for (int i = 0; i < 31; i++) {
        if ((diff >> i & 1) == 1) {
            y = f[i][y];
        }
    }

    if (x != y) {
        for (int i = 30; i >= 0; i--) {
            if (f[i][x] != f[i][y]) {
                x = f[i][x];
                y = f[i][y];
            }
        }
        x = f[0][x];
    }
    return x;
}

Tarjan

  • 离线查询算法，时间复杂度为 \(O((n+m)\log{n})\)。更精确的复杂度分析可以使用反阿克曼函数。
  • 原理：每当处理完一个子树，就将该子树的根节点和其父节点合并，特别注意合并的方向是 \(f[y]=x\)。然后我们会遍历包含当前节点 \(x\) 的查询，如果另一个节点 \(y\) 访问过，则 \(\operatorname{lca}(x,y)=\operatorname{find}(y)\)。至于为什么是这样，可以通过分类讨论得到。注意 \(q\) 需要像无向图一样，为单个查询存储双向边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void tarjan(int x, List<Integer>[] g, boolean[] vis, UnionFind uf, List<int[]>[] q, int[] ans) {
    vis[x] = true;
    for (int y : g[x]) {
        if (!vis[y]) {
            tarjan(y, g, vis, uf, q, ans);
            uf.union(x, y); // 注意 f[y] = x
        }
    }

    for (int[] t : q[x]) {
        int y = t[0], i = t[1];
        if (vis[y]) {
            ans[i] = uf.find(y);
        }
    }
}

树链剖分

  • 预处理时间复杂度为 \(O(n)\)，查询时间复杂度为 \(O(\log{n})\)。
  • 原理：将树划分为若干重链，树中的每条路径不会包含超过 \(\log{n}\) 条不同的重链，所以查询的时间复杂度为 \(O(\log{n})\)。第一次 DFS 得到每个节点的父节点，深度，以及根据子树大小得到每个节点的重子节点。第二次 DFS 通过优先遍历重子节点，再遍历轻子节点，从而得到每个节点所在重链的头节点。然后就可以进行查询，通过比较 \(x,y\) 所在重链的头节点，来向上跳跃，最终得到 \(\operatorname{lca}\)。
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
private static void dfs1(int x, int fa, List<Integer>[] g, int[] f, int[] d, int[] s, int[] h) {
    f[x] = fa;
    s[x] = 1; h[x] = -1;
    for (int y : g[x]) {
        if (y != fa) {
            d[y] = d[x] + 1;
            dfs1(y, x, g, f, d, s, h);
            s[x] += s[y];
            if (h[x] == -1 || s[h[x]] < s[y]) {
                h[x] = y;
            }
        }
    }
}

private static void dfs2(int x, int head, List<Integer>[] g, int[] f, int[] h, int[] t) {
    t[x] = head;
    if (h[x] == -1) {
        return;
    }
    dfs2(h[x], head, g, f, h, t);
    for (int y : g[x]) {
        if (y != f[x] && y != h[x]) {
            dfs2(y, y, g, f, h, t);
        }
    }
}

private static int lca(int x, int y, int[] f, int[] d, int[] t) {
    while (t[x] != t[y]) {
        if (d[t[x]] > d[t[y]]) {
            x = f[t[x]];
        } else {
            y = f[t[y]];
        }
    }
    return d[x] < d[y] ? x : y;
}

强连通分量

例题

Tarjan

  • 时间复杂度为 \(O(n+m)\)。
  • 原理：\(dfn[x]\) 表示节点 \(x\) 的 DFS 编号；\(low[x]\) 表示节点 \(x\) 能够到达的节点的最小的 DFS 编号。我们将图看作一棵树，并定义四种边，那么强连通分量的根节点就是该分量中第一个被遍历到的节点，满足 \(dfn[x]=low[x]\)，所以，过程很复杂，难以描述，直接看 wiki 吧。（注意使用的时候，将 \(dfn\) 初始化为 \(-1\)，并且对所有节点调用该算法前，需要判断 \(dfn=-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
private static int dfnCnt, sccCnt;

private static void tarjan(int x, List<Integer>[] g, int[] dfn, int[] low, Deque<Integer> stk, boolean[] on, int[] scc, int[] size) {
    dfn[x] = low[x] = dfnCnt++;
    stk.push(x);
    on[x] = true;

    for (int y : g[x]) {
        if (dfn[y] == -1) {
            tarjan(y, g, dfn, low, stk, on, scc, size);
            low[x] = Math.min(low[x], low[y]);
        } else if (on[y]) {
            low[x] = Math.min(low[x], dfn[y]);
        }
    }

    if (dfn[x] == low[x]) {
        for (int y = -1; y != x; ) {
            y = stk.pop();
            on[y] = false;
            scc[y] = sccCnt;
            size[sccCnt]++;
        }
        sccCnt++;
    }
}

图论

https://ligh0x74.github.io/2023/10/31/图论/

作者

Ligh0x74

发布于

2023-10-31

更新于

2024-09-02

许可协议

评论

×