罗罗编程学习记录
本页内容 展开查看

02.12.2 网络流与二分图匹配

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶

覆盖范围

  • 最大流 Ford-Fulkerson 与 Dinic
  • 匈牙利算法二分图最大匹配
  • KM 算法带权二分图
  • 最小割最大流定理

高频题速览

编号 题目 难度 频率
02.12.2-001 最大流 Ford-Fulkerson 高级 ★★★
02.12.2-002 Dinic 算法 高级 ★★★
02.12.2-003 匈牙利算法二分图最大匹配 进阶 ★★★★
02.12.2-004 KM 算法带权二分图 高级 ★★★
02.12.2-005 匈牙利 vs KM 区别 基础 ★★★★
02.12.2-006 最小割最大流定理 进阶 ★★★
02.12.2-007 二分图最小顶点覆盖 进阶 ★★★
02.12.2-008 网络流应用场景 基础 ★★★

02.12.2-001 最大流 Ford-Fulkerson

频率 ★★★ | 难度 高级

一句话结论

Ford-Fulkerson 反复在残量网络中找增广路,沿途增加流量;找不到增广路时当前流量即最大流;用 DFS 找增广路,时间复杂度 O(E * maxFlow)。

概念解释

  • 残量网络:每条边有残量 capacity - flow。
  • 增广路:从源点到汇点的路径,沿途残量 > 0。
  • 反向边:用于退流,保证算法正确。

原理流程

  1. 建残量网络(正向边 + 反向边)。
  2. DFS 找增广路。
  3. 增广路上更新流量和残量。
  4. 找不到增广路时结束。

代码 / 示例

class Edge {
    int to, rev, cap;
    Edge(int to, int rev, int cap) { this.to = to; this.rev = rev; this.cap = cap; }
}
class FordFulkerson {
    private final java.util.List<Edge>[] graph;
    private final boolean[] visited;
    private final int n;

    FordFulkerson(int n) {
        this.n = n;
        graph = new java.util.List[n];
        for (int i = 0; i < n; i++) graph[i] = new java.util.ArrayList<>();
        visited = new boolean[n];
    }
    void addEdge(int from, int to, int cap) {
        graph[from].add(new Edge(to, graph[to].size(), cap));
        graph[to].add(new Edge(from, graph[from].size() - 1, 0));
    }
    int dfs(int u, int t, int flow) {
        if (u == t) return flow;
        visited[u] = true;
        for (Edge e : graph[u]) {
            if (!visited[e.to] && e.cap > 0) {
                int d = dfs(e.to, t, Math.min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to].get(e.rev).cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t) {
        int flow = 0;
        while (true) {
            java.util.Arrays.fill(visited, false);
            int f = dfs(s, t, Integer.MAX_VALUE);
            if (f == 0) break;
            flow += f;
        }
        return flow;
    }
}

常见误区

  • 误区:不建反向边;正解:反向边用于退流,保证算法正确。
  • 误区:DFS 用 BFS;正解:Ford-Fulkerson 用 DFS,Dinic 用 BFS 分层。

追问 / 延伸

  • Q:时间复杂度? A:O(E * maxFlow),maxFlow 大时慢。
  • Q:为什么需要反向边? A:退流,即之前增广的流量可以撤回,保证算法找到最优解。

02.12.2-002 Dinic 算法

频率 ★★★ | 难度 高级

一句话结论

Dinic 用 BFS 分层(构建 level graph),再用 DFS 在分层图中找阻塞流;重复直到汇点不可达;时间复杂度 O(V^2 * E),实际快很多。

概念解释

  • BFS 分层:给每个节点分 level。
  • 阻塞流:在分层图中尽可能多地增广。
  • 重复:BFS 重建分层图,DFS 找阻塞流。

原理流程

  1. BFS 分层(只走残量 > 0 的边)。
  2. DFS 在分层图中找增广路(level[v] = level[u] + 1)。
  3. 重复直到汇点不可达。

代码 / 示例

class Dinic {
    private final java.util.List<Edge>[] graph;
    private final int[] level, iter;
    private final int n;

    Dinic(int n) {
        this.n = n;
        graph = new java.util.List[n];
        for (int i = 0; i < n; i++) graph[i] = new java.util.ArrayList<>();
        level = new int[n]; iter = new int[n];
    }
    void addEdge(int from, int to, int cap) {
        graph[from].add(new Edge(to, graph[to].size(), cap));
        graph[to].add(new Edge(from, graph[from].size() - 1, 0));
    }
    boolean bfs(int s, int t) {
        java.util.Arrays.fill(level, -1);
        java.util.Deque<Integer> q = new java.util.ArrayDeque<>();
        level[s] = 0; q.offer(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (Edge e : graph[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.offer(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int i = iter[u]; i < graph[u].size(); i++) {
            Edge e = graph[u].get(i);
            if (e.cap > 0 && level[u] < level[e.to]) {
                int d = dfs(e.to, t, Math.min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to].get(e.rev).cap += d;
                    return d;
                }
            }
            iter[u]++;
        }
        return 0;
    }
    int maxFlow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            java.util.Arrays.fill(iter, 0);
            int f;
            while ((f = dfs(s, t, Integer.MAX_VALUE)) > 0) flow += f;
        }
        return flow;
    }
}

常见误区

  • 误区:BFS 不分层;正解:BFS 分层,DFS 只走 level+1 的边。
  • 误区:iter 不重置;正解:每次 BFS 后重置 iter。

追问 / 延伸

  • Q:Dinic 时间复杂度? A:O(V^2 * E),实际远快。
  • Q:单位容量网络? A:O(E * sqrt(V))。

02.12.2-003 匈牙利算法二分图最大匹配

频率 ★★★★ | 难度 进阶

一句话结论

二分图左部每个节点尝试找右部匹配;若右部节点已匹配,则尝试让已匹配的左部节点重新找其他右部;找到则增广,时间复杂度 O(V * E)。

概念解释

  • 二分图:左部 L、右部 R,边只在 L-R 之间。
  • 匹配:边集,任意两条边不共享端点。
  • 增广路:从未匹配点出发,交替走非匹配边和匹配边,到未匹配点。

原理流程

  1. 对每个左部节点 u:
  2. DFS 尝试找右部节点 v。
  3. v 未匹配:直接匹配。
  4. v 已匹配:尝试让 v 的匹配左部节点重新找其他右部。
  5. 找到则增广。

代码 / 示例

class Hungarian {
    private final java.util.List<Integer>[] graph; // 左部 -> 右部
    private final int[] matchR; // 右部 -> 左部
    private final boolean[] visited;
    private final int n, m;

    Hungarian(int n, int m) {
        this.n = n; this.m = m;
        graph = new java.util.List[n];
        for (int i = 0; i < n; i++) graph[i] = new java.util.ArrayList<>();
        matchR = new int[m];
        java.util.Arrays.fill(matchR, -1);
        visited = new boolean[n];
    }
    void addEdge(int u, int v) { graph[u].add(v); }
    boolean dfs(int u) {
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                if (matchR[v] == -1 || dfs(matchR[v])) {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int maxMatching() {
        int count = 0;
        for (int u = 0; u < n; u++) {
            java.util.Arrays.fill(visited, false);
            if (dfs(u)) count++;
        }
        return count;
    }
}

常见误区

  • 误区:visited 标记右部节点;正解:标记右部节点,防止重复尝试。
  • 误区:matchR 初始化 0;正解:初始化 -1 表示未匹配。

追问 / 延伸

  • Q:时间复杂度? A:O(V * E)。
  • Q:最大匹配 = 最小顶点覆盖? A:二分图中成立(Konig 定理)。

02.12.2-004 KM 算法带权二分图

频率 ★★★ | 难度 高级

一句话结论

KM 求带权二分图最大权完美匹配;给左部节点顶标 l[u]、右部节点顶标 r[v],满足 l[u] + r[v] >= w(u,v);相等子图(l[u]+r[v]==w(u,v))的完美匹配即最大权匹配。

概念解释

  • 顶标:左部 l[u]、右部 r[v]。
  • 相等子图:l[u]+r[v] == w(u,v) 的边。
  • 完美匹配:每个节点都匹配。

原理流程

  1. 初始化顶标:l[u] = max(w(u,v)),r[v] = 0。
  2. 对每个左部节点 u,在相等子图中找增广路。
  3. 找不到则调整顶标(降低左部、提高右部),扩大相等子图。
  4. 重复直到所有左部节点匹配。

代码 / 图示

KM 算法:
  顶标 l[u], r[v],满足 l[u]+r[v] >= w(u,v)
  相等子图:l[u]+r[v] == w(u,v)
  相等子图完美匹配 = 最大权匹配

常见误区

  • 误区:KM 求最大匹配;正解:KM 求最大权完美匹配。
  • 误区:顶标初始化 0;正解:左部初始化为最大权边。

追问 / 延伸

  • Q:时间复杂度? A:O(V^3)。
  • Q:KM 和匈牙利区别? A:匈牙利求最大匹配(无权),KM 求最大权完美匹配(带权)。

02.12.2-005 匈牙利 vs KM 区别

频率 ★★★★ | 难度 基础

一句话结论

匈牙利求无权二分图最大匹配(最多匹配多少对);KM 求带权二分图最大权完美匹配(权值最大的完美匹配);两者都是二分图匹配,但目标不同。

概念解释

  • 匈牙利:无权,最大匹配。
  • KM:带权,最大权完美匹配。
  • 复杂度:匈牙利 O(V*E),KM O(V^3)。

原理流程

  1. 只问最多匹配多少对:匈牙利。
  2. 问权值最大的完美匹配:KM。
  3. 两者都是增广路思想。

代码 / 图示

算法     目标           复杂度
匈牙利   最大匹配       O(V*E)
KM       最大权完美匹配  O(V^3)

常见误区

  • 误区:KM 是匈牙利的带权版;正解:KM 用顶标和相等子图,思路不同。
  • 误区:KM 求最大匹配;正解:KM 求最大权完美匹配。

追问 / 延伸

  • Q:二分图最大匹配和最大流关系? A:二分图最大匹配 = 最大流(源点连左部、左部连右部、右部连汇点)。
  • Q:KM 能求非完美匹配吗? A:可以,加虚拟节点。

02.12.2-006 最小割最大流定理

频率 ★★★ | 难度 进阶

一句话结论

最大流 = 最小割:残量网络中从源点到汇点的最大流等于把图分成 S(含源点)和 T(含汇点)的最小割(S-T cut 的容量和)。

概念解释

  • 割:把节点分成 S 和 T,S 含源点,T 含汇点。
  • 割容量:从 S 到 T 的边容量和。
  • 最大流 = 最小割。

原理流程

  1. 求最大流。
  2. 残量网络中从源点 DFS,可达节点为 S。
  3. S 到 T 的边就是最小割。

代码 / 图示

最大流 = 最小割
S:源点可达节点
T:汇点不可达节点
S -> T 的边容量和 = 最大流

常见误区

  • 误区:最小割是边数最少;正解:最小割是容量和最小。
  • 误区:最大流和最小割无关;正解:最大流 = 最小割。

追问 / 延伸

  • Q:最小割怎么求? A:最大流后,残量网络中源点可达节点为 S,S 到 T 的边。
  • Q:最小割应用? A:最小点割、最大闭合权图。

02.12.2-007 二分图最小顶点覆盖

频率 ★★★ | 难度 进阶

一句话结论

二分图中,最小顶点覆盖(选最少的点覆盖所有边)= 最大匹配(Konig 定理);最大独立集 = 节点总数 - 最大匹配。

概念解释

  • 顶点覆盖:选点集,每条边至少有一个端点在点集中。
  • 最小顶点覆盖:最少点数。
  • Konig 定理:二分图最小顶点覆盖 = 最大匹配。

原理流程

  1. 求最大匹配。
  2. 最小顶点覆盖 = 最大匹配。
  3. 最大独立集 = n - 最大匹配。

代码 / 图示

Konig 定理:
  最小顶点覆盖 = 最大匹配
  最大独立集 = n - 最大匹配

常见误区

  • 误区:Konig 定理适用于所有图;正解:只适用于二分图。
  • 误区:最大独立集 = 最大匹配;正解:最大独立集 = n - 最大匹配。

追问 / 延伸

  • Q:最小顶点覆盖怎么求具体点? A:从左部未匹配点出发 DFS(交替路),左部未访问 + 右部已访问 = 最小顶点覆盖。
  • Q:最大团? A:二分图中最大团 = 最大独立集。

02.12.2-008 网络流应用场景

频率 ★★★ | 难度 基础

一句话结论

网络流用于:二分图匹配、最大闭合权图、最小割(如项目选择)、多源多汇(加超级源汇)、最大密度子图;建模是关键。

概念解释

  • 二分图匹配:源点连左部、右部连汇点。
  • 最大闭合权图:选正权点和负权点,闭合集。
  • 最小割:项目选择、最小点割。

原理流程

  1. 判断问题是否能转化为网络流。
  2. 建图(节点、边、容量)。
  3. 跑最大流。
  4. 从最大流结果提取答案。

代码 / 图示

应用:
  二分图匹配 -> 最大流
  项目选择 -> 最小割
  最大闭合权图 -> 最小割
  多源多汇 -> 超级源汇

常见误区

  • 误区:网络流只能求最大流;正解:最小割、最大闭合权图等都是最大流的应用。
  • 误区:网络流建模简单;正解:建模是难点,需要把问题转化为图。

追问 / 延伸

  • Q:网络流工程中用得多吗? A:竞赛多,工程少,但某些调度问题用。
  • Q:最大流和动态规划区别? A:网络流是图上的,DP 是序列上的。

待整理清单

  • [ ] 最大闭合权图
  • [ ] 费用流
  • [ ] 上下界网络流