有权图算法问题总结

[kyle-ip]

最短路径

最短路径问题（Shortest Path）：从图上的某一点到达另外一点，找到一条路径，使得权值之和最小（在下文中，路径的长短即权值之和的大小）。

• 对于无权图的最短路径，只需要用广度优先遍历（BFS）方法求解，选取最少边的路径即可；而对于有权图，有时途经更多边的路径权值之和可能会更小。

• 单源最短路径求解：起始点是固定点，求解从源点 src 到图中任一点的最短路径，常用的算法是 Dijkstra 算法和 Bellman-Ford 算法。

• 如要求出图中所有点的最短路径，则需要适用于求所有点对的最短路径算法：Floyd 算法。

为了更方便地描述算法，先给出有权图的 Java 实现（省略细节）。

有权边 WeightedEdge（兼容有向、无向）：

public class WeightedEdge implements Comparable<WeightedEdge> {
    
    // 起点，终点，权值
    private final int v, w, weight;
    
    public WeightedEdge(int v, int w, int weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    
    // ...
}

有权图 WeightedGraph：

public class WeightedGraph {
    
    // 顶点数，边数
    private int V;
    private int E;
    
    /**
     * 邻接表：使用红黑树描述
     * [
     *      0: {1: 3, 2: 2, 3: -2},
     *      1: (2: 2, 3: 2, 4: 1)
     * ]
     */
    private TreeMap<Integer, Integer>[] adj;
    
    // 获取权值
    public int getWeight(int v, int w) {
        if (hasEdge(v, w)) {
            return adj[v].get(w);
        }
        throw new IllegalArgumentException(String.format("No edge %d-%d", v, w));
    }
    
     // 边是否存在
    public boolean hasEdge(int v, int w) {
        return adj[v].containsKey(w);
    }
    
    // ...
}

Dijkstra 算法

该算法适用于无负权边的带权图（权值 >= 0，符合大多数情况），数组变量 dis 表示从 0 到 i 的最小权值之和，每轮循环：

• 找到当前没有过访问的（没有求解出最短路径的）节点中，距离当前节点路径最短的节点。

• 确认这个节点的最短路径即为当前大小。

• 根据这个节点的最短路径大小，更新其他节点的路径长度。

过程解析：由于不存在负权边，如果从 O 到达 A 的权值，小于从 O 到达其它任意顶点的权值（由于不可能经由其他点绕回来总和更小），则此时 O-A 即为最短路径。

     3
 +------[B]
 |   1   |
[O]-----[A]
 |   4   |
 +------[C]

对于满足第 1 步的顶点，确定已求得最短路径后可用于迭代求其他邻接点的最短路径：

从 A 出发，尝试判断经由 A 到达其它邻接点的权值之和是否会比当前从 O 出发的方案更小（dis 数组的值），是则更新：dis[B] = min(dis[A] + weight[A][B])。比如 O-A-B 比 O-B 小：

     3
 +------[B]
 |   1   | 1
[O]-----[A]
 |   4   | 1
 +------[C]

基本实现：

public class WeightedGraph {
    // ...
    
    public Iterable<Integer> shortestPathDijkstra(int src, int dest) {
        int[] dis = new int[V], prev = new int[V];
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dis[src] = 0;
        prev[src] = src;

        // visited 用于记录“已确定最短距离”的顶点。
        boolean[] visited = new boolean[V];

        // 使用最小堆用于高效提取 dis 最小的顶点（同一个点可能存在多份）。
        // 而最小值必然是最近更新的结果，即距离已更新点 v 最近的点。
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{src, 0});

        // 每轮循环可决定（到达）一个点的最短距离。
        while (!pq.isEmpty()) {

            // 1. 利用最小堆找到 dis 最小值的顶点。
            int v = pq.poll()[0];

            // 2. 更新顶点状态，如果该点已经确定最短路径则跳过。
            if (visited[v]) {
                continue;
            }
            visited[v] = true;

//            // 找到到达终点的最短路径可提前结束（对于 Bellman Ford 算法，由于存在松弛操作，不能提前终止）。
//            if (v == dest) {
//                break;
//            }

            // 3. 根据刚才确定的解，更新邻接顶点的 dis 值。
            for (int w : adj(v)) {

                // 如果 w 未确定最短路径，且其目前的 dis 值大于经由 v 到达 w 的距离，则更新 dis[w] 并添加到最小堆。
                // 比如：
                //           3
                //       +------[w]
                //       |       | 1
                //      [0]-----[v]
                //           1
                // 此时 w 仍未确定，需要重新放入最小堆，用作下次继续更新。
                if (!visited[w] && dis[w] > dis[v] + getWeight(v, w)) {
                    dis[w] = dis[v] + getWeight(v, w);
                    pq.add(new int[]{w, dis[w]});
                    prev[w] = v;
                }
            }
        }

        // 根据 prev 数组求整个路径。
        LinkedList<Integer> ret = new LinkedList<>();
        if (!visited[dest]) {
            return ret;
        }
        int cur = dest;
        while (cur != src) {
            ret.addFirst(cur);
            cur = prev[cur];
        }
        ret.addFirst(src);
        return ret;
    }
}

实现细节：

• 使用最小堆用于高效提取 dis 最小的顶点（log(n)），而最小值必然是最近更新的结果，即距离已更新点 v 最近的点。

• 每轮循环可以决定到达一个点的最短距离：

  • 利用最小堆找到 dis 最小值的顶点。如果该点已经确定最短路径则跳过，否则更新顶点状态为已访问。

• 根据刚才确定的解，循环更新所有邻接顶点的 dis 值：如果 w 未确定最短路径，且其目前的 dis 值大于经由 v 到达 w 的距离，则更新 dis[w] 并添加到最小堆；否则需要重新放入最小堆，用作下次继续更新。

  • 遍历过程中用 prev 数组不断记录当前节点的上一个节点。

• 最终用 prev 数组反向求出整个路径。

时间复杂度：

• 由于每轮循环内都需要一层循环来找到 dis 最小的顶点，因此 Time: O(V^2)。

• 上面的实现利用了最小堆（优先级队列）记录边，无需判断所有顶点，因此 Time: O(E*log(E))。

• 使用索引堆（Index Heap），可进一步优化到 Time: O(V*log(E))。

点击链接可查看动图：Dijkstra Visualzation (usfca.edu)

Bellman-Ford 算法

相比起 Dijkstra Bellman-Ford 算法的优势是不受负权边的影响，是在无向图中也成立的有向图算法（因为无向图可以理解为对于每条边都有反向边的有向图）。

假设 dis[v] 是从 s 到 v 的经过边数不超过 k 的最短距离。

• 初始 dis[s] = 0，其余点为 MAX。

• 定义 松弛操作（Repaxation）：寻找每多经过一条边，可得到的最短距离（迂回计算最短路径）。进行第 k 次松弛操作，即找到从 s 到 b 的经过边数不超过 k+1 的最短距离。比如下图中 O-B-A 比 O-A 多经过一条边，但权值之和比 O-A 小，因此可更新最短路径：

     8
 +------[B]
 |   6   | -3
[O]-----[A]

dis[A] = min(dis[A], dis[B] + weight[B][A]);
dis[B] = min(dis[A], dis[A] + weight[A][B]);

• 对所有边进行 [1, v) 共 v-1 轮松弛操作，则求出到所有点经过的边数最多为 [1, v) 的最短路径。

负权环：环的路径和为负数，因此每绕一圈，权值之和会变得更小，这种情况下不存在最短路径。要判断负权环，只需要在第 v-1 轮松弛操作后多进行一轮，根据 dis 值是否还会更新，即可判断是否存在负权环、最短路径是否有意义。

   [2]
 3/   \-6
[0]---[1]
    2

在无向图中，存在负权边即等于存在负权环，在有向图中则不一定。

基本实现：

public class WeightedGraph {
    // ...
    public Iterable<Integer> shortestPathBellmanFord(int src, int dest) {
        int[] dis = new int[V], prev = new int[V];
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dis[src] = 0;

        // 进行 v-1 轮松弛操作。
        for (int pass = 1; pass < V; pass++) {

            // 在每轮操作中对所有的边进行松弛操作：遍历每个顶点的邻接顶点，即取出每条边。
            for (int v = 0; v < V; v++) {
                for (int w : adj(v)) {
                    // 如果 dis[v] 已被更新过，且 dis[w] 目前的 dis 值大于经由 v 到达 w 的距离，则更新 dis[w]。
                    if (dis[v] != Integer.MAX_VALUE && dis[w] > dis[v] + getWeight(v, w)) {
                        dis[w] = dis[v] + getWeight(v, w);
                        prev[w] = v;
                    }
                }
            }
        }

        // 判断是否有负权环：进行第 v 轮松弛操作。
        boolean hasNegCycle = false;
        for (int v = 0; v < V; v++) {
            for (int w : adj(v)) {
                if (dis[v] != Integer.MAX_VALUE && dis[w] > dis[v] + getWeight(v, w)) {
                    hasNegCycle = true;
                }
            }
        }

        LinkedList<Integer> ret = new LinkedList<>();
        // 存在负权环，返回空。
        if (hasNegCycle) {
            System.out.println("exist negative cycle");
            return ret;
        }
        // dis[dest] 没有被更新，表示 dest 不在路径上，返回空。
        if (dis[dest] == Integer.MAX_VALUE) {
            return ret;
        }
        int cur = dest;
        while (cur != src) {
            ret.addFirst(cur);
            cur = prev[cur];
        }
        ret.addFirst(src);
        return ret;
    }
}

实现细节：

• 对于 V 个节点的图，进行 V-1 次松弛操作：

  • 在每轮松弛操作中，遍历每个顶点 v，对于每个顶点再遍历其邻接顶点 w，取出每条边（v-w）。

• 如果 dis[v] 已被更新过，且 dis[w] 目前的 dis 值大于经由 v 到达 w 的距离，则更新 dis[w]。

  • 遍历过程中用 prev 数组不断记录当前节点的上一个节点。

• 进行第 V 轮松弛操作来判断是否有负权环，如果存在负权环，则直接返回空。

• 判断 dis[dest] 是否已被更新（非 MAX），如在刚才的松弛操作中未被更新，表示终点不在路径上，返回空。

• 最终用 prev 数组反向求出整个路径。

时间复杂度：O(V*E)

SPFA 算法

实际上很多情况下不需要 v-1 轮松弛操作就可以找到最短路径，因此后续的松弛操作是浪费的。SPFA 算法在 Bellman-Ford 算法的基础上优化，使用一个队列记录只关注的顶点，每次只对这些顶点的邻边进行松弛操作。

Floyd-Warshall 算法

前面两种算法只能求出单源最短路径，而 Floyd-Warshall 算法的特点是可以一次过求出所有点对最短路径，以及图的直径（所有点对最短路径的最大值）。

注意，所有点对的最短路径不是单源最短路径算法的叠加。

区别于 Bellman-Ford，其比较对象不是一条边，而是经由某点到达此处的最短路径的距离（可能已经过多条边）。

• 初始化，如果 v-w 边存在，有 dis[v][w] = weight[v][w]、dis[v][v] = 0；否则 dis[v][w] = MAX。

• 循环执行以下过程，其中：

  • t 循环相当于松弛操作，每轮循环求解出中间绕过 [0, t] 这些点的最短路径。

  • v、w 循环寻找最短路径的起始点和终止点。

for (int t = 0; t < V; t++) {
    for (int v = 0; v < V; v++) {
        for (int w = 0; w < V; w++) {
            if (dis[v][t] + dis[t][w] < dis[v][w]) {
                dis[v][w] = dis[v][t] + dis[t][w];
            }
        }
    }
}

Floyd 算法同样要判断是否存在负权环：最终判断 dis[v][v] 是否有小于 0 的值，有则表示存在负权环，最短路径无意义。

     8
 +------[t]
 |   6   | -3
[v]-----[w]

基本实现：

public class WeightedGraph {
    // ...
    public Iterable<Integer> shortestPathFloydWarshall(int src, int dest) {

        // dis[v][w] 表示 从 v 到 w 的最短路径长度。
        int[][] dis = new int[V][V];
        int[] prev = new int[V];
        Arrays.fill(prev, -1);
        for (int v = 0; v < V; v++) {
            Arrays.fill(dis[v], Integer.MAX_VALUE);
        }
        for (int v = 0; v < V; v++) {
            dis[v][v] = 0;
            for (int w : adj(v)) {
                dis[v][w] = getWeight(v, w);
            }
        }
        // 相当于松弛操作，每轮循环求解出中间绕过 [0, t] 这些点的最短路径。
        for (int t = 0; t < V; t++) {
            // 寻找最短路径的起始点和终止点。
            for (int v = 0; v < V; v++) {
                for (int w = 0; w < V; w++) {

                    //      8
                    //  +------[t]
                    //  |   6   | -3
                    // [v]-----[w]
                    if (dis[v][t] != Integer.MAX_VALUE && dis[t][w] != Integer.MAX_VALUE && dis[v][t] + dis[t][w] < dis[v][w]) {
                        dis[v][w] = dis[v][t] + dis[t][w];
                        prev[w] = v;
                    }
                }
            }
        }
        for (int v = 0; v < V; v++) {
            if (dis[v][v] < 0) {
                // 存在负权环，返回空。
                return Collections.emptyList();
            }
        }

        LinkedList<Integer> ret = new LinkedList<>();
        int cur = dest;
        while (cur != src) {
            ret.addFirst(cur);
            cur = prev[cur];
        }
        ret.addFirst(src);
        return ret;
    }
}

实现细节：

• Floyd-Warshall 算法的比较对象是经由某点到达某点的最短路径，因此需要使用二维的 dis 数组，且遍历过程中也是需要用 prev 数组记录当前节点的上一个节点。

• 与 Bellman-Ford 算法类似，Floyd-Warshall 算法也有 松弛操作，区别在于其每轮循环求解出中间绕过 [0, t] 这些点的最短路径。

• 最终也需要判断是否遍历 dis 数组的所有点对，判断是否有负值（表示负权环），返回空。

时间复杂度：O(V^3)

点击链接可查看动图：Floyd-Warshall All-Pairs Shortest Path (usfca.edu)

总结

三种算法对比（对于稀疏图，V 远远小于 E）：

• Dijkstra：不能包含负权边，Time: O(V*log(E))。

• Bellman-Ford：可包含负权边，可检测负权环，Time: O(V*E)。

• Floyd-Warshall：可包含负权边，可检测负权环，Time: O(V^3)。

在上述的 Floyd-Warshall 算法的实现中，利用 prev 数组反向求解具体路径的写法存在一定问题，您可以找出并解决这个问题吗？

参考

• Dijkstra's algorithm - Wikipedia

• Bellman–Ford algorithm - Wikipedia

• Floyd–Warshall algorithm - Wikipedia

• Data Structure Visualization (usfca.edu)

最小生成树

在图论领域，有权图（Weight Graph）最经典的问题是最小生成树问题（Minimum Spanning Tree）：对于一个 n 个节点的 连通图，求出包含原图 n 个节点、且确保所有边权值之和最小的连通子图，则为 最小生成树（MST）。

有权图与其最小生成树：

先给出有权图的 Java 实现（省略细节），有权边 WeightedEdge（兼容有向、无向）：

public class WeightedEdge implements Comparable<WeightedEdge> {
    
    // 起点，终点，权值
    private final int v, w, weight;
    
    public WeightedEdge(int v, int w, int weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    
    // ...
}

有权图 WeightedGraph：

public class WeightedGraph {
    
    // 顶点数，边数
    private int V, E;
    
    /**
     * 邻接表：使用红黑树描述
     * [
     *      0: {1: 3, 2: 2, 3: -2},
     *      1: (2: 2, 3: 2, 4: 1)
     * ]
     */
    private TreeMap<Integer, Integer>[] adj;
    
    // 获取权值
    public int getWeight(int v, int w) {
        if (hasEdge(v, w)) {
            return adj[v].get(w);
        }
        throw new IllegalArgumentException(String.format("No edge %d-%d", v, w));
    }
    
     // 边是否存在
    public boolean hasEdge(int v, int w) {
        return adj[v].containsKey(w);
    }
    
    // ...
}

连通性判断

对于一个图，可求解出最小生成树的前提是该图为 连通图，即图中任意两个节点之间都能找到至少一条路径相连。

对于非连通图，每个连通子图都称为一个 连通分量。

因此判断图是否连通可使用以下深度优先遍历（DFS）算法：

• 使用变量 int left 记录待访问节点数（初始化为图节点总数 V），数组 boolean[] visited 记录节点访问状态（避免重复访问）。

• 从任意一个节点 v 出发深度优先遍历图，每经过一个未被访问的邻接节点 w 即标记为已访问 visited[w] = true;，并把待访问节点数 -1 left--，否则跳过。

• 当从 v 出发的深度优先遍历结束，表示已找到一个连通分量。此时判断待访问节点数 left 是否为 0，是则表示刚才已完成整图遍历，该图为连通图，否则为非连通图。

基本实现如下：

Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[V];

// 从 0 出发遍历图，判断图是否联通。
stack.push(0);
int left = V - 1;
visited[0] = true;
while (!stack.empty()) {
    int v = stack.pop();
    for (int w : adj(v)) {
        if (visited[w]) {
            continue;
        }
        // 每遇到一个未访问的邻接顶点，则 left--。
        left--;
        visited[w] = true;
        stack.push(w);
    }
}

return left == 0;

切分定理（Bipartite）

将一个图中的顶点分为两部分，称为一个 切分。其中一条边的两个端点属于切分不同的两边，则该边称为 横切边。

如果考虑边的权值，横切边的最短边就属于最小生成树（切分定理）。

二分图

基于切分的定义引入二分图的概念：在图中能找到一个切分，其所有的边都是横切边，则该图为 二分图（Bipartite Graph）：所有顶点可以分成边不相交的两部分（A 部分的点只于 B 部分相连，不与内部的点相连），所有的边的两个端点隶属于不同的部分。

二分图的概念常见于无权图的匹配问题（Matching）、最大流问题（Max Flow），经典的算法有 Hungarian 算法。

介绍切分的概念，是为了引入在遍历图的过程中，把节点划归到不同子集的技巧，这种做法在介绍 Prim 算法时再做具体说明。

并查集（Union Find）

并查集是一种多叉树，其包含两种基本操作：合并和查询。假设待加入并查集的节点共 n 个。

• 初始化：对于所有的 n 个点 [0, n-1]，代表每个点的集合都初始化为自身，比如 0 => {0}, 1 => {1}, ..., n-1 => {n-1}。

• 合并：将两个节点所表示的集合（表示为树）合并为一个集合，即将代表其中一个节点的树的根，嫁接到另一个节点表示的树的孩子上。

• 查找：查找节点所在的集合，即根节点。

由于本文旨在总结最小生成树相关算法，并查集不是重点，只做简要说明并直接给出实现代码。

public class UnionFind {

    // 父节点：parent[p] 即 p 的父节点。
    private final int[] parent;

    // 集合大小（优化树结构）
    private final int[] size;

    // 初始化：[0, n) 所有节点的父节点都是它自身，集合大小都为 1。
    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 查询：从给定节点迭代向其父节点查询，直到根节点。并更新沿途访问节点的根节点。
    public int find(int p) {
        if (p != parent[p]) {
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }

    // 判断两个点是否相连。
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并：两个给定的节点迭代查询到根节点，如果它们有共同根节点则直接返回，否则把其中的一个的根节点接到另一个根节点上（节点数更多的作为根节点）。
    public void union(int p, int q) {
        // 不去重（根的值相同也合并）。
        // parent[find(parent, p)] = find(parent, q);

        // 去重（根的值相同不合并）。
        int pRoot = find(p), qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (size[p] > size [q]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }
    }
    
    // 求大小：某个节点的大小等于其根节点的节点数。
    public int size(int p) {
        return size[find(p)];
    }

    // 联通分量个数：父节点为其自身的点的数量。
    public int cc() {
        int cnt = 0;
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == i) {
                cnt++;
            }
        }
        return cnt;
    }
}

有了以上基础，就可以开始进入最小生成树的求解了。

Kruskal 算法

Kruskal 算法本质是贪心算法：每次尽量使用短边。

每次按权值从小到大选取图上不会构成环的短边，直到覆盖所有顶点。

• 每次选择一个最短边，如果这个边没有形成环，则相当于对一个切分选择了最短横切边。

• 判断是否成环：可以使用 DFS（O(V+E)）或 并查集（接近 O(E)）。

并查集用于存放图的节点，并判断节点是否直接或间接相连。

比如 1-2、2-3 被添加到 uf，当 1-3 被尝试添加到 uf 时，会被判断为 1 和 3 已通过 2 相连，因此不再处理。

   [3]
 X    \ ✔
[1]---[2]
    ✔

在这里直接给出使用并查集可在判断路径是成环时，优化节点查找效率的结论（接近 O(E)），感兴趣的话可以自己探究一下。

基本实现：

public class WeightedGraph {
    // ...
    public Iterable<WeightedEdge> mstKruskal() {
        // 省略环的判断，以下代码仅在连通图中有效。

        // 把所有边添加到 edges。
        List<WeightedEdge> edges = new ArrayList<>(E);
        for (int v = 0; v < V; v++) {
            for (int w : adj(v)) {
                // 不重复添加。
                if (v < w) {
                    edges.add(new WeightedEdge(v, w, getWeight(v, w)));
                }
            }
        }
        
        // 按权值从小到大排序。
        Collections.sort(edges);

        // 使用并查集判断每次取出的边是否与先前已取出的边形成环，不成环则收集。
        
        List<WeightedEdge> mst = new ArrayList<>(V - 1);
        UnionFind uf = new UnionFind(V);
        for (WeightedEdge edge : edges) {
            
            // 比如 1-2 与 2-3 都已添加到 uf 中，则下次通过 uf 可判断 1 和 3 已相连，不需要再添加到 mst。
            if (uf.isConnected(edge.getV(), edge.getW())) {
                continue;
            }
            mst.add(edge);
            uf.union(edge.getV(), edge.getW());
        }
        return mst;
    }
}

实现细节：

• 使用一个数组 edges 记录所有的边，并按权值从小到大排列。

• 初始化一个大小为 V 的并查集 uf，默认所有的边都不成环（表示为并查集中的点都不相连）。

• 遍历集合 edges，如果该边的两个顶点（v 和 w）在 uf 中没有相连，则添加到 mst 集合中，并在 uf 中连接 v 和 w。

时间复杂度：O(E*log(E))

点击链接可查看动图：Kruskal MST Visualzation (usfca.edu)

Prim 算法

Prim 算法将图中的顶点分为两部分，其核心是不断操作更新切分：

• 从边数之比为 1: V-1 开始，选取两个顶点（切分 from）、与其他点（切分 to）分别组成两个切分。

• 选取这两个切分的最短横切边，添加到 MST 集合，并把顶点更新到切分 from（由于切分更新，此时横切边可能发生改变）。

• 循环执行，直到切分 to 的所有节点都被转移到切分 from（不存在切分），即得到 MST。

先直接给出基本实现，再进一步分析实现的细节：

public class WeightedGraph {
    // ...
    public Iterable<WeightedEdge> mstPrim() {
        // 省略环的判断，以下代码仅在连通图中有效。

        // 标记节点当前归属的切分。
        boolean[] visited = new boolean[V];
        visited[0] = true;

        // 使用最小堆（堆顶元素必然是最短边），初始化添加顶点 0 的所有邻接边。
        Queue<WeightedEdge> pq = new PriorityQueue<>();
        for (int w : adj(0)) {
            pq.add(new WeightedEdge(0, w, getWeight(0, w)));
        }

        List<WeightedEdge> mst = new ArrayList<>();
        while (!pq.isEmpty()) {
            // 每轮循环取出最短边，如果边的两点已归属于 true 切分，表示该边非横切边，跳过。
            WeightedEdge minEdge = pq.remove();
            if (visited[minEdge.getV()] && visited[minEdge.getW()]) {
                continue;
            }
            // 收集最短横切边，并把该边当前归属于 false 切分的点划归 true。
            mst.add(minEdge);
            int newV = visited[minEdge.getV()] ? minEdge.getW() : minEdge.getV();
            visited[newV] = true;

            // 遍历新加入的 true 切分的点的邻接顶点，把未访问（即归属于 false 切分）的顶点添加到最小堆。
            for (int w : adj(newV)) {
                if (!visited[w]) {
                    pq.add(new WeightedEdge(newV, w, getWeight(newV, w)));
                }
            }
        }
        return mst;
    }
}

与其他 DFS、BFS 算法的实现类似，Prim 算法的实现也是基于 boolean[] visited 数组，只是数组的值有了另一层面的意义：用于表示节点划归到不同的切分。对于初始节点 0，划归到 true 切分，其余节点为 false 切分。

使用最小堆存放节点 0 的所有邻边，判断条件为权值的大小，使得随时可以 O(log(E)) 的代价取出最短边。

循环执行以下步骤直到最小堆为空，其间使用 mst 集合收集最小生成树的边，最终返回即可：

• 遍历最小堆，每轮循环取出堆顶的最短边，如果该边的两点已归属于 true 切分，表示该边非横切边，因此跳过。

• 否则收集最短边到 mst 集，并把改横切边上，当前归属于 false 切分的端点 v 划归到 true 切分。

• 遍历新加入 true 的节点 v 的所有邻接节点 w，把其中未访问（即还属于 false 切分）的节点添加到最小堆。

时间复杂度：由于使用了最小堆，可快速找到最短横切边，时间复杂度从 O(V*E) 优化到 O(E*log(E))，如改用索引堆（Index Heap）则可以进一步优化到 O(E*log(V))。

点击链接可查看动图：Prim MST Visualzation (usfca.edu)

总结

本文介绍了最小生成树问题两种最经典的算法，实际上除此之外还有 Fredman-Tarjan 算法（Time: O(E+V*log(V))）、Chazelle 算法（Time: O(E*)），限于篇幅就不再一一介绍了，感兴趣的话可以自行查阅相关资料。

参考

• Kruskal's algorithm - Wikipedia

• Prim's algorithm - Wikipedia

• Data Structure Visualization (usfca.edu)

最大流问题

网络流（Network Flow） 是图算法领域中很重要的一种模型。其网络表示为有向有权图，常用于表示水管、交通、网络等。

对于一个表示网络流模型的有向图包含以下特征：

• 源点（Source）：模型中只有一个，入度为 0 的点。

• 汇点（Sink）：模型中只有一个，出度为 0 的点。

• 容量（Capacity）：模型中的边上容纳的流不能超过其容量，即边上的非负权值。

• 流量（Flow）：模型中每有一条流（路径）经过一条边，则该边上的流量 +1。

• 源点的流出量等于汇点的流入量，对于图中的其他每个顶点，流入量等于流出量。

在此基础上要考虑网络流模型中可容纳的最大流量，即为 最大流问题（Max Flow）。

先给出有权图的 Java 实现（省略细节），有权边 WeightedEdge：

public class WeightedEdge implements Comparable<WeightedEdge> {
    
    // 起点，终点，权值
    private final int v, w, weight;
    
    public WeightedEdge(int v, int w, int weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    
    // ...
}

有权图 WeightedGraph：

public class WeightedGraph {
    
    // 顶点数，边数
    private int V, E;
    
    /**
     * 邻接表：使用红黑树描述
     * [
     *      0: {1: 3, 2: 2, 3: -2},
     *      1: (2: 2, 3: 2, 4: 1)
     * ]
     */
    private TreeMap<Integer, Integer>[] adj;
    
    // 获取权值
    public int getWeight(int v, int w) {
        if (hasEdge(v, w)) {
            return adj[v].get(w);
        }
        throw new IllegalArgumentException(String.format("No edge %d-%d", v, w));
    }
    
     // 边是否存在
    public boolean hasEdge(int v, int w) {
        return adj[v].containsKey(w);
    }
    
    // ...
}

Ford-Fulkerson 思想

要解决最大流问题（求出从源点发出、到汇点接收的流量），首先要理解 Ford-Fulkerson 思想。

重要的几点：

• 选优思路是填满容量最小的边，但如果只关注边的容量，无法达到全局最优（先把源点填满，但中间有边未饱和）。

• 思考 反向边：可以对一条已经存在流量的边，反向抵消流量，此时看作一条反向边。比如下图中容量为 5 的边：

  [A]
 2↑ ↓3
  [B]

• 残量图（Residual Graph）：描述图中的边剩余可经过的流量。假设在原图中边 v-w 的容量为 c，流量为 f，则残量图中 v-w 边的权值为 c-f，w-v 的权值为 f。

• 增广路径（Augmenting Path）：在残量图中找到从源点 s 到汇点 ``、所有的权值都大于 0 的路径，其流量为路径中边的最小权值。

Ford-Fulkerson 思想可理解为在原图出发创建残量图，在残量图中不断寻找增广路径，每找到一条增广路径则图中流量增加，直到无法再找到增广路径为止，即求得最大流（上图为原图，下图为残量图与增广路径）。

时间复杂度：O(maxflow * E)

Edmonds-Karp 算法

基于 Ford-Fulkerson 思想，目的是寻找增广路径，其步骤是：

• 创建残量图：在初始时原图中每条边的流量都为 0，因此对于残量图，所有正向边的流量都等于原图对应的容量，反向边流量都为 0。

• 使用广度优先遍历（BFS）在残量图中寻找从源点到汇点的增广路径（权值为 0 则不能通过）。

• 每找到一条增广路径，可计算出其流量等于最小权值边的权值 f，因此把原图中对应路径上的边流量 +f、把残量图中对应的边权值更新为 c-f，反向边权值更新为 f。

• 重复执行第二步继续寻找增广路径、更新残量图权值和原图流量。

增广路径

如何在残量图上寻找增广路径？如上所述采用广度优先遍历即可。

采用一个 int[] prev 数组记录当前节点的前一个节点，初始化为 -1 可表示节点未被访问过，>= 0 表示已经访问过且存储上一个节点编号（初始化为 -1，表示未更新）。

int[] prev = new int[V];
Arrays.fill(prev, -1);
prev[s] = s;

在 BFS 循环过程中，取出的节点 cur 首先判断是否为汇点，是则退出循环。否则遍历其邻接节点 next。如果 next 未被访问过，且 cur 与 next 在残量图上的边权值大于 0，则添加到路径数组 prev 中。

// 广度优先遍历。
Queue<Integer> q = new LinkedList<>();
q.add(s);
while(!q.isEmpty()){
    int cur = q.remove();
    // 遇到汇点，退出循环。
    if (cur == t) {
        break;
    }

    // 遍历邻接节点，如邻接节点未访问过，且在残量图上、与邻接节点的边权值大于 0，则添加到路径。
    for (int next: rG.adj(cur)) {
        if(prev[next] == -1 && rG.getWeight(cur, next) > 0) {
            prev[next] = cur;
            q.add(next);
        }
    }
}

在退出循环时，利用 prev 数组还原增广路径并返回（必须到达汇点 t）。

// 还原增广路径并返回（必须到达汇点）。
LinkedList<Integer> res = new LinkedList<>();
if (prev[t] == -1) {
    return res;
}
int cur = t;
while(cur != s){
    res.addFirst(cur);
    cur = prev[cur];
}
// 最后把源点加上。
res.addFirst(s);

完整代码如下：

public class WeightedGraph {
    // ...
    private List<Integer> getAugmentingPath(int s, int t, WeightedGraph rG) {

        // 记录顶点是否被遍历过、当前顶点的前一个顶点（初始化为 -1，>= 0 表示已经遍历过，且存储上一个节点）。
        int[] prev = new int[V];
        Arrays.fill(prev, -1);
        prev[s] = s;
        
        // 广度优先遍历。
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while(!q.isEmpty()){
            int cur = q.remove();
            // 遇到汇点，退出循环。
            if (cur == t) {
                break;
            }

            // 遍历邻接节点。
            for (int next: rG.adj(cur)) {
                // 邻接节点未访问过，且在残量图上、与邻接节点的边权值大于 0，则添加到路径。
                if(prev[next] == -1 && rG.getWeight(cur, next) > 0) {
                    prev[next] = cur;
                    q.add(next);
                }
            }
        }

        // 还原增广路径并返回（必须到达汇点）。
        LinkedList<Integer> res = new LinkedList<>();
        if (prev[t] == -1) {
            return res;
        }
        int cur = t;
        while(cur != s){
            res.addFirst(cur);
            cur = prev[cur];
        }
        res.addFirst(s);
        return res;
    }
}

求解最大流

有了求增广路径的方法，求解最大流就很容易实现了，简单讲解一下实现细节。

创建残量图：残量图与原图有相同的结构，其中原图的容量即残量图的权值，且原图的反向边在残量图中表示为权值 0（初始状态时由于正向边没有流量，反向边也没有流量抵消）。

WeightedGraph rG = new WeightedGraph(V, true);
for (int v = 0; v < V; v++) {
    for (int w : adj(v)) {
        // 原图的容量 => 残量图的权值，反向为 0（初始时正向边没有流量，反向边也没有流量抵消）。
        rG.addEdge(v, w, getWeight(v, w));
        rG.addEdge(w, v, 0);
    }
}

创建完成后，在残量图上循环执行最大流 maxFlow 的统计：

在残量图中循环寻找增广路径，每找到一条增广路径则访问其上的所有边，统计边的最小权值（即流量） f 并累加到最大流上。

int f = Integer.MAX_VALUE;
for (int i = 1; i < augPath.size(); i++) {
    int v = augPath.get(i - 1), w = augPath.get(i);
    f = Math.min(f, rG.getWeight(v, w));
}
maxFlow += f;

根据增广路径更新残量图的流量：遍历增广路径的每条边，考虑其两个顶点 v 和 w，正向减去 f，反向加上 f（边 v-w 的流量就是残量图的反向边的权值，也即可抵消的流量）。

for (int i = 1; i < augPath.size(); i++) {
    int v = augPath.get(i - 1), w = augPath.get(i);
    // 正向减去增广路径的最小权值，反向加上增广路径的最小权值。
    rG.setWeight(v, w, rG.getWeight(v, w) - f);
    rG.setWeight(w, v, rG.getWeight(w, v) + f);
}

循环以上步骤直到找不到增广路径，此时 maxFlow 的值即为网络流模型的最大流。完整代码：

public class WeightedGraph {
    // ...
    public int maxFlowEdmondsKarp(int s, int t) {
        // 省略参数校验，以下代码默认在有向有权图、图节点数 > 2 且源点不等于汇点时有效。
        
        int maxFlow = 0;

        // 创建残量图。
        WeightedGraph rG = new WeightedGraph(V, true);
        for (int v = 0; v < V; v++) {
            for (int w : adj(v)) {
                // 原图的容量 => 残量图的权值，反向为 0（初始时正向边没有流量，反向边也没有流量抵消）。
                rG.addEdge(v, w, getWeight(v, w));
                rG.addEdge(w, v, 0);
            }
        }

        // 在残量图中寻找增广路径。
        while (true) {
            List<Integer> augPath = getAugmentingPath(s, t, rG);

            // 找不到增广路径，已求出最大流，返回。
            if (augPath.size() == 0) {
                return maxFlow;
            }
            // 访问增广路径上所有的边，计算边最小权值，累计到最大流上。
            int f = Integer.MAX_VALUE;
            for (int i = 1; i < augPath.size(); i++) {
                int v = augPath.get(i - 1), w = augPath.get(i);
                f = Math.min(f, rG.getWeight(v, w));
            }
            maxFlow += f;

            // 根据增广路径更新 rG 的流量。
            for (int i = 1; i < augPath.size(); i++) {
                int v = augPath.get(i - 1), w = augPath.get(i);
                // 正向减去增广路径的最小权值，反向加上增广路径的最小权值。
                rG.setWeight(v, w, rG.getWeight(v, w) - f);
                rG.setWeight(w, v, rG.getWeight(w, v) + f);
            }
        }
        // 边 v-w 的流量，即残量图的反向边的权值（可抵消的流量）。
        // int flow = rg.getWeight(w, v);
    }
}

时间复杂度：O(V*E^2)

总结

最大流算法应用广泛，其中最典型的一类就是匹配问题（Matching）。其本质是在图上选边，边的集合中不允许一个顶点出现两次。

因此匹配问题是基于二分图的建模，其中包括最大匹配（匹配数量最多的方案）、完全匹配（所有的顶点都纳入匹配方案中，必然是最大匹配）。

利用最大流思想解决匹配问题：

• 建立网络流模型，引入虚拟的源点和汇点、分别与二分图两边的顶点相连。

• 将原图的无向边改为有向边，所有的边容量设为 1。

• 再参照最大流算法即可求得最大匹配数（即为最大流的值）。

本文只是介绍了求解最大流问题最基础的 Edmonds-Karp 算法，实际上这类问题还有很多复杂的优化，比如 Dinic 算法、MPM 算法。

另外普林斯顿大学的算法课程上也有一道经典的棒球比赛问题（COS 226 Programming Assignment. Baseball Elimination），感兴趣的朋友可以自行查阅相关资料、思考一下如何运用网络流模型解决实际问题。

参考

• Maximum flow problem - Wikipedia

• COS 226 Programming Assignment: Baseball Elimination (princeton.edu)

• Data Structure Visualization (usfca.edu)