最小生成树Kruskal和Prim算法

开始讨论无向带权图。

基本概念

• 最小生成树：给定一个无向图，如果该图的一个生成子图是一棵树，则称该树为生成树(Spanning Tree)。
• 最小生成树：无向带权图中权值之和最小的生成树，称之为最小生成树(Minimum Spanning Tree)。
• 切分：将图中的顶点分为两部分的划分，就称为一个切分。
• 横切边：如果一个边的两个端点属于不同的切分，则称该边为横切边。

(G是二分图存在图G的一个切分，使得图中的所有边都是横切边。)

无向带权图类的实现

/*Ice_spring 2020/3/26*/
import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;

// 图的邻接表表示，无向无权图
public class WeightedGraph implements Cloneable {
    private int V; // 顶点数
    private int E; // 边数
    private TreeMap<Integer, Integer>[] adj; // 邻接集合，存放邻接点和对应边权值（可以是浮点型）

    public WeightedGraph(String filename){
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
            adj = new TreeMap[V];

            for(int i = 0; i < V; i ++)
                adj[i] = new TreeMap<>();
            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");

            for(int i=0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                int weight = scanner.nextInt();
                // 本代码只处理简单图
                if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
                if(adj[a].containsKey(b)) throw new IllegalArgumentException("Parallel Edges are detected!");
                adj[a].put(b, weight);
                adj[b].put(a, weight);
            }
        }
        catch(IOException e){
            e.printStackTrace();//打印异常信息
        }
    }
    public void validateVertex(int v){
        // 判断顶点v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回顶点数
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 顶点 v 到 w 是存在边
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }
    public Iterable<Integer> adj(int v){
        // 返回值可以是TreeSet，不过用 Iterable 接口更能体现面向对象
        // 返回和顶点 v 相邻的所有顶点
        validateVertex(v);
        return adj[v].keySet();
    }
    public int getWeight(int v, int w){
        // v-w 边的权值
        if(hasEdge(v, w))
            return adj[v].get(w);
        throw new IllegalArgumentException(String.format("No Edge %d-%d ", v, w));
    }
    public int degree(int v){
        // 返回节点 v 的度，即与该顶点相邻的顶点个数
        validateVertex(v);
        return adj[v].size(); //
    }
    public void removeEdge(int v, int w){
        // 删除 v-w 边
        validateVertex(v);
        validateVertex(w);
        adj[v].remove(w);
        adj[w].remove(v);
    }
    @Override
    public Object clone() {
        try {
            WeightedGraph cloned = (WeightedGraph) super.clone();
            cloned.adj = new TreeMap[V];
            for(int v = 0; v < V; v ++){
                cloned.adj[v] = new TreeMap<>();
                for(Map.Entry<Integer, Integer> entry: adj[v].entrySet())// 遍历Map的方式
                    cloned.adj[v].put(entry.getKey(), entry.getValue());
            }
            return cloned;
        }catch (CloneNotSupportedException e){
            e.printStackTrace();
        }
        return null;
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n",V, E));
        for(int v = 0; v < V; v ++){
            // 编程好习惯 i,j,k 作索引, v,w 作顶点
            sb.append(String.format("%d : ", v));

            for(Map.Entry<Integer,Integer>entry: adj[v].entrySet())
                sb.append(String.format("(%d: %d)", entry.getKey(), entry.getValue()));

            sb.append('\n');
        }
        return sb.toString();
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt");
        System.out.println(g);
    }
}

Kruskal算法

Kruskal算法过程
Kruskal算法按权值递增的次序选择合适的边来构造最小生成树。
对于图G(V,E)，设VT为生成树中的顶点，ET为生成树中的边，Kruskal算法具体过程如下：
（1）初始化VT=V，ET=空，即每个顶点看做一颗独立的树，此时的T是一个含有V个顶点的森林；
（2）按G的边的权值递增顺序依次从E-ET中选择一条边，若加入这条边后不构成回路，则将其加入ET，否则继续选择；
（3）重复过程（2）直到ET中有n-1条边，此时T(VT,ET)就是最小生成树。
Kruskal算法求解图的最小生成树是一种贪心策略，它的正确性可以由切分定理来保证。
切分定理
横切边中权值最小的边一定属于最小生成树。
时间复杂度
由于算法的最大时间开销在边权值的排序上，故kruskal算法时间复杂度是O(ElogE)，因此该算法适合于边稀疏的图。
算法的实现
首先给出要存到最小生成树中的边类。

public class WeightedEdge implements Comparable<WeightedEdge>{
    private int v, w, 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 int compareTo(WeightedEdge another){
        // 定义比较
        return weight - another.weight;
    }
    @Override
    public String toString(){
        return String.format("(%d-%d: %d)", v, w, weight);
    }
}

另外为了判断新加入的边是否和已经选择过的边构成环，使用并查集来快速动态判断环。

public class UnionFind {

    private int[] parent;
    private int[] sz; // sz[i]表示以 i 为根的集合中元素个数

    public UnionFind(int n) {
        parent = new int[n];
        sz = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i; // 初始每个点都自成一个集合
            sz[i] = 1;
        }
    }
    public void unionElements(int p, int q){
        // 将两个元素合并到一个集合, p 连到 q 上，也可以 q 连 p
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return;
        parent[pRoot] = qRoot; // 这里的pRoot 此后就不会被find到
        sz[qRoot] += sz[pRoot];
    }
    public boolean isConnected(int p, int q){
        // 判定p q 是否在一个集合
        return find(p) == find(q);
    }
    public int find(int p) {
        // 寻找p 所在的集合
        if (p != parent[p])
            parent[p] = find(parent[p]);
        return parent[p];
    }
    public int size(int p){
        // p 所在集合有几个元素
        return sz[find(p)];
    }
}

kruskal算法：

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

public class Kruskal {
    // 最小生成树的结果用 ArrayList 保存相应的 n-1 条边
    private WeightedGraph G;
    private ArrayList<WeightedEdge> mst;
    public Kruskal(WeightedGraph G){
        this.G = G;
        mst = new ArrayList<>();

        CC cc = new CC(G);
        if(cc.count() > 1)return;
        ArrayList<WeightedEdge> edges = new ArrayList<>();
        for(int v = 0; v < G.V(); v ++)
            for(int w: G.adj(v))
                if(v < w)// 避免 2-0, 0-2 这样的重复存储
                    edges.add(new WeightedEdge(v, w, G.getWeight(v, w)));
        Collections.sort(edges);

        UnionFind uf = new UnionFind(G.V());
        for(WeightedEdge edge: edges){
            int v = edge.getV();
            int w = edge.getW();
            if(!uf.isConnected(v, w)){
                mst.add(edge);
                uf.unionElements(v, w);
            }
        }
    }
    public ArrayList<WeightedEdge> result(){
        return mst;
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt");
        Kruskal kl = new Kruskal(g);
        System.out.println(kl.result());
    }
}

Prim算法

Prim算法过程
Prim算法不断添加新的顶点和权值最小的横切边来构造最小生成树，是切分定理最直接的应用。
对于图G(V,E)，设VT为生成树中的顶点，ET为生成树中的边，Prim算法具体过程如下：
（1）初始化VT={u0}，ET=空，此时的T是一棵只有一个顶点的空树；
（2）在G所有的uVT，vV-VT的边(u,v)中找到一条权值最小的边(u0,v0)加入集合ET，同时将v0并入集合VT。(该过程就是不断添加权值最小的横切边)
（3）重复过程（2）直到所有顶点都在VT中，此时T(VT,ET)就是最小生成树。
时间复杂度
经典Prim算法的时间复杂度是O(V^2)，适合于求解边稠密的图。
算法的实现

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

public class Prim {
    // 最小生成树的结果用 ArrayList 保存
    private WeightedGraph G;
    private ArrayList<WeightedEdge> mst;

    public Prim(WeightedGraph G){
        this.G = G;
        mst = new ArrayList<>();

        CC cc = new CC(G);
        if(cc.count() > 1)return;
        ArrayList<WeightedEdge> edges = new ArrayList<>();
        boolean visited[] = new boolean[G.V()];
        visited[0] = true;// 初始
        for(int i = 1; i < G.V(); i ++){
            WeightedEdge minEdge = new WeightedEdge(-1, -1, 0x3f3f3f3f);
            for(int v = 0; v < G.V(); v ++)
                if(visited[v])
                    for(int w: G.adj(v))
                        if(!visited[w] && G.getWeight(v, w) < minEdge.getWeight())
                            minEdge = new WeightedEdge(v, w, G.getWeight(v, w));
            mst.add(minEdge);
            visited[minEdge.getV()] = true; // 扩充切分
            visited[minEdge.getW()] = true;
        }
    }
    public ArrayList<WeightedEdge> result(){
        return mst;
    }
    public static void main(String args[]){
        WeightedGraph g = new WeightedGraph("g.txt");
        Prim prim = new Prim(g);
        System.out.println(prim.result());
    }
}

Prim算法的一个优化
只需要从当前访问过的顶点的临边中选取最小权值的边而不必要访问全部的边，为此可以使用优先队列(最小堆)这种数据结构。由于每条边都会进出优先队列一次，故优化后的时间复杂度是O(ElogE)。

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class Prim_Heap {

    // 最小生成树的结果用 ArrayList 保存
    private WeightedGraph G;
    private ArrayList<WeightedEdge> mst;

    public Prim_Heap(WeightedGraph G) {
        this.G = G;
        mst = new ArrayList<>();

        CC cc = new CC(G);
        if (cc.count() > 1) return;
        ArrayList<WeightedEdge> edges = new ArrayList<>();
        boolean visited[] = new boolean[G.V()];
        visited[0] = true;// 初始

        Queue<WeightedEdge> pq = new PriorityQueue<>();
        for(int w: G.adj(0))
            pq.add(new WeightedEdge(0, w, G.getWeight(0, w)));
        while(!pq.isEmpty()){
            WeightedEdge minEdge = pq.remove();
            if(visited[minEdge.getV()] && visited[minEdge.getW()])
                continue;
            mst.add(minEdge);

            int newv = visited[minEdge.getV()] == true ? minEdge.getW(): minEdge.getV();
            visited[newv] = true;// 拓展切分
            for(int w: G.adj(newv))
                if(!visited[w])
                    pq.add(new WeightedEdge(newv, w, G.getWeight(newv, w)));
        }
    }

    public ArrayList<WeightedEdge> result() {
        return mst;
    }

    public static void main(String args[]) {
        WeightedGraph g = new WeightedGraph("g.txt");
        Prim_Heap prim = new Prim_Heap(g);
        System.out.println(prim.result());
    }
}