最小生成树

带权图

在之前的文章中，介绍的都是无向无权图，那本篇开始介绍无向带权图

如果将上述的图看做是一个交通系统的话，那么边的权重就可以代表为距离。为了表示带有权重的图，我们建立一个 WeightedGraph 类来表示带权图。

同无权图 AdjSet 一样，我们从如下格式的文件读取内容生成图

第一行 7 表示总共有 7 个节点，12 表示有 12 条件，下面表示两两相邻的节点，以及之间的权重，例如 0 1 2 表示节点 0 与节点 1 相邻，之间的权重为 2。

WeightedGraph 类如下，代码大部分同 AdjSet 类：

import java.io.File;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class WeightedGraph{
    private int V;
    private int E;
    // adj[i] 是一个 HashMap，键为相邻的节点，值为边上的权重
    private HashMap<Integer, Integer>[] adj;

    public WeightedGraph(String path) {
        File file = new File(path);
        Scanner scanner = null;

        // 从 txt 文件读取建立图，大部分同 AdjSet 类
        try {
            scanner = new Scanner(file);
            this.V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException("V can't be negative");
            }
            adj = new HashMap[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new HashMap<>();
            }

            this.E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("E can't be negative");
            }

            for (int i = 0; i < E; i++) {
                int v = scanner.nextInt();
                int w = scanner.nextInt();
                int weight = scanner.nextInt();

                if (v == w) {
                    throw new IllegalArgumentException("存在自环边");
                }
                if (adj[v].containsKey(w)) {
                    throw new IllegalArgumentException("存在平行边");
                }

                adj[v].put(w, weight);
                adj[w].put(v, weight);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            scanner.close();
        }
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }

    public int getWeight(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return adj[v].get(w);
    }

    public int degree(int v) {
        validateVertex(v);
        return adj[v].size();
    }

    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }

    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v].keySet();
    }

    public void validateVertex(int v) {
        if (v < 0 && v >= V) {
            throw new IllegalArgumentException("节点超过 [0, V) 的范围");
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
        for (int v = 0; v < this.V; v++) {
            stringBuilder.append(String.format("%d : ", v));
            for (Map.Entry w: adj[v].entrySet()) {
                stringBuilder.append(String.format("(%d: %d) ", w.getKey(), w.getValue()));
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }
}

最小生成树

首先介绍生成树的概念，假设图中有 $V$ 个顶点，如果能找到图中 $V - 1$ 条边这 $V$ 个节点连接起来，那么就说这 V 个节点与 V - 1 条边形成的图叫做这个图的生成树。

例如图的 DFS 遍历以及 BFS 遍历就会形成一个生成树

只要图中的 $V - 1$ 条边将图中的 $V$ 个顶点联通起来，那么就是图的一个生成树，所以一个图有很多的生成树，所谓的最小生成树，就是生成树边上的权值加起来最小

那么最小生成树有什么应用呢? 如果将这个图看做是交通系统，找出最小生成树就是找到一种耗费最低的方式将所有站点连通起来的布局方案。

切分定理

下面介绍切分定理，这个定理被用来寻找最小生成树。首先什么叫切分，所谓切分就是把节点分为两部分

上图中节点 $0, 5, 4$ 被划分一部分，其余节点为另一部分。切分的方式有很多种，随意你进行切分，只要将图中的节点划分为两部分即可。

引入了切分的概念，下面继续引入横切边的概念。所谓的横切边指的是将两个不同部分节点连接起来的边，例如对于上面的划分，有如下横切边

上面被标记为绿色的边就是横切边，可以看到横切边的两端是两个不同部分的节点。

介绍完必须的概念之后，引入切分定理：

切分定理：对于任意一个切分，这种切分形成的横切边中，权值最小的横切边一定在最小生成树中

这个定理很好证明，我们根据切分将图分为两部分

这两部分之间的边就是横切边，可以观察到横切边将这两个部分连接在了一起，为了使得生成树连通，一定要在横切边中选择一条边，而为了得到最小生成树，那当然选择的是权值最小的横切边，所以说权值最小的横切边一定在最小生成树中。

Kruskal 算法

Kruskal 算法是求的最小生成树的一种算法，他的思想很简单，就是每次取图中最小的边，只要这条边没有已经选取的边形成环。例如对于下图

首先选择图中最短的两条边，即权值为 1 的两条边 1-2 与 3-4

下面继续选择权值最小的边，选择 0-5、0-1，这两条边的权值为 2

继续选择权值最小的边，此时选择 1-4，权值为 3

继续选择，此时应该选择 5-2 与 1-3 两条边，它们的权值为 4，但是我们发现选择 5-2 就会形成一个环，选择 1-3 也会形成环，所以这两条边不能选，生成树中可不能有环的。除开这两条边继续选择，发现 5-1、3-6 这两条边的权值为 5，权值最小，但是选择 5-1 就会形成环，所以不选 5-1，只选择 3-6

这个时候我们已经找到了 6 条边将这 7 个顶点连接起来，即找到了一个最小生成树

Kruskal 的算法思想很简单，就是贪心，每次选择权重最小的边，但是怎么证明这种贪心策略是对的。这就需要用到切分定理。

每次我们选择最小的边，我们只需要让这条边是一个切分的横切边就行，这种切分很好做，让这条边两个节点属于不同的部分即可，根据切分定理这条横切边一定是最小生成树中的一条边。如果这条边与选择的边形成了一个环，这说明找不到一个切分，使得这条边的所有横切边中最短的边，所以不能选择它。

在代码的实现方向，每次我们找到一个最短的边时，需要判断是否构成一个环，例如我们找到边 5-1，需要判断添加这条边是否构成一个环，其实就是在检测在添加这条边之前节点 5 和节点 1 是否连通，如果是连通，添加这条边后就会形成环。

每次都需要判断两个节点需要连通，可以使用 DFS 来做，但是这样做复杂度太高，借助并查集这种数据结构可以很方便的判断两个节点是否连通，只需要判断它们是否在一个集合中即可，如果对于并查集不熟，可以参考这篇文章。

并查集的实现如下：

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int getSize() {
        return parent.length;
    }

    private int find(int index) {
        if (index < 0 || index >= parent.length) {
            throw new IllegalArgumentException("参数错误");
        }

        while (index != parent[index]) {
            index = parent[index];
        }
        return index;
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }

        if (rank[pRoot] <= rank[qRoot]){
            parent[pRoot] = parent[qRoot];
            if (rank[pRoot] == rank[qRoot]) {
                rank[qRoot]++;
            }
        } else {
            parent[qRoot] = parent[pRoot];
        }
    }
}

我们需要一个类来保存边的信息，这里我们新建一个 WeightedEdge 类：

public class WeightedEdge {
    private int v;
    private int w;
    private int weight;

    public WeightedEdge(int v, int w, int weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public int getV() {
        return v;
    }

    public int getW() {
        return w;
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return String.format("(%d-%d: %d)", v, w, weight);
    }
}

Kruskal 算法实现如下：

import java.util.ArrayList;
import java.util.Collections;

public class Kruskal {
    private WeightedGraph graph;
    public ArrayList<WeightedEdge> result = new ArrayList<>();

    public Kruskal(WeightedGraph graph) {
        this.graph = graph;
        int V = graph.V();

        // 将所有的边添加进集合中
        ArrayList<WeightedEdge> edges = new ArrayList<>();
        for (int v = 0; v < V; v++) {
            for (int w: graph.adj(v)) {
                if (v < w) {
                    edges.add(new WeightedEdge(v, w, graph.getWeight(v, w)));
                }
            }
        }
        
        
	    // 根据边的权值大小，从小到大排序
        Collections.sort(edges, (w1, w2) -> w1.getWeight() - w2.getWeight());
        UnionFind unionFind = new UnionFind(V);
        for (WeightedEdge edge: edges) {
            int v = edge.getV();
            int w = edge.getW();
            // 如果之前不连通
            if (!unionFind.isConnected(v, w)) {
                result.add(edge);
                unionFind.unionElements(v, w);
            }
        }
    }

    public Iterable<WeightedEdge> result() {
        return result;
    }
}

Prim 算法

Prim 算法也是有关最小生成树的算法，它的思想同切分定理密切相关。因为对于每一个切分，权值最小的横切边一定在最小生成树中。Prim 算法就在遍历节点的过程中，将遍历到的节点与未遍历的节点作为两部分形成一个切分，然后遍历此时所有的横切边，在此边作为最小生成树的一条边。

每次遍历到一个节点即可找到一条横切边，当遍历到最后一个节点时，就能找到 $V-1$ 条边，即可形成一个生成树，并且根据切分定理，这个生成树一定是最小生成树。

Prim 算法最后的结果是同 Kruskal 算法相同的。

在代码的实现方面，因为每次产生一次新的切分，都要找到所有的横切边进行遍历然后找到最小的横切边，这个过程我们可以使用优先队列进行实现。

当遍历到一个节点时，新的横切边的产生都与这个遍历到的节点相连，我们只要将新的横切边添加到队列中即可，不用遍历节点寻找所以的横切边，另外这是一个优先队列，即队首元素它的权重是最小的，我们也不用查找最小边的炒作，直接取出队首元素即可。

另外，可能你会注意到，当遍历到一个新的节点，产生一个新的切分时，之前的横切边可能不是横切边了，即优先队列中的边不是所有的边都是横切边。仔细想想，这个并没有影响，因为虽然不是所有的边都是横切边，但是所有的横切边都在队列里，我们从队列中取出边时进行判断，不是横切边直接忽略即可，完全不影响我寻找最小的横切边。

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Prim {
    private WeightedGraph graph;
    private boolean[] visited;
    private ArrayList<WeightedEdge> result = new ArrayList<>();

    public Prim(WeightedGraph graph) {
        this.graph = graph;
        PriorityQueue<WeightedEdge> priorityQueue = 
            new PriorityQueue<>((w1, w2) -> w1.getWeight() - w2.getWeight());
        this.visited = new boolean[graph.V()];
        
        visited[0] = true;
        for (int w: graph.adj(0)) {
            priorityQueue.add(new WeightedEdge(0, w, graph.getWeight(0, w)));
        }

        while (!priorityQueue.isEmpty()) {
            WeightedEdge edge = priorityQueue.remove();
            int v = edge.getV();
            int w = edge.getW();
            // 不是横切边直接忽略
            if (visited[v] && visited[w]) {
                continue;
            }
            result.add(edge);
            visited[w] = true;
            // 添加新的横切边
            for (int next: graph.adj(w)) {
                priorityQueue.add(new WeightedEdge(w, next, graph.getWeight(w, next)));
            }
        }

    }

    public Iterable<WeightedEdge> result() {
        return result;
    }
}