4.3 最小生成树

4.3 最小生成树

定义:图的生成树是含有所有顶点的无环连通子图,加权图的最小生成树(MST)是一棵权值最小的生成树

约定

• 只限于连通图:由定义,最小生成树只存在于连通图
• 权值可为0或者负数
• 所有边的权重都不同,否则MST不唯一

4.3.1 原理

4.3.3.1 切分定理

切分:即把图所有顶点分成两个非空且不重叠的部分

横切边即连接这两部分,两端各属于不同部分的边

切分定理:加权图中,给定任意的切分,其横切边中权重最小者一定属于图的最小生成树

证明:反证法:设T为图的最小生成树,e为权重最小的横切边且不在T中,由树的性质,T中加入一条边必定成环,则连接e,此时环中至少含有另一条横切边f,而f权重大于e,则删去f保留e,的到更小的树,与前提矛盾

4.3.3.2 最小生成树的贪心算法

算法:使用切分定理:V个顶点的任意加权连通图中:在一种切分下,选出权重最小横切边,一定含于MST中;另一种切分下,同样操作;最终当选出V-1条不同的横切边时,即为MST

4.3.2 加权无向图的数据类型:加权边Edge->加权无向图EdgeWeightedGraph

加权边API:public class Edge implements Comparable

public class Edge implements Comparable<Edge>{
    private final int v;
    private final int w;
    private final double weight;
    public Edge(int v, int w, double weight){
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    public double weight(){ return weight;}
    public int either(){ return v; }//一个端点
    public int other(int vertex){//对侧端点
        if (vertex == v) return w;
        else if (vertex == w) return  v;
        else throw new RuntimeException("Inconsistent edge");
    }
    public int compareTo(Edge that){//自然比较
        if (this.weight() < that.weight()) return -1;
        else if(this.weight() > that.weight()) return 1;
        else return 0;
    }
    //每条边输出格式:点-点 权重
    public String toString(){
        return String.format("%d-%d %.2f",v,w,weight);
    }
}

加权无向图API:public class EdgeWeightedGraph

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class EdgeWeightedGraph {
    private final int V;//总点数
    private int E;//总边数
    private Bag<Edge>[] adj;//邻接表
    public EdgeWeightedGraph(int V){
        this.V = V;
        this.E = 0;
        adj = (Bag<Edge>[])new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<>();
    }
    public EdgeWeightedGraph(In in){
        this(in.readInt());
        int E = in.readInt();
        for (int i = 0; i < E; i++)
            addEdge(new Edge(in.readInt(),in.readInt(),in.readDouble()));
    }
    public void addEdge(Edge e){
        int v = e.either(), w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }
    public int V(){ return V;}
    public int E(){ return E;}
    //与v关联边
    public Iterable<Edge> adj(int v){return adj[v];}
    //所有边
    public Iterable<Edge> edges(){
        Bag<Edge> b = new Bag<>();
        for (int v = 0; v < V; v++)
            for (Edge e: adj(v))
                //忽略自环
                if (e.other(v) > v) b.add(e);
        return b;
    }
    public String toString(){
        String s = V + " vertices, " + E + " edges\n";
        for (int v = 0; v < V; v++){
            s += v + ": ";
            for (Edge e:adj(v))
                s += e + " ";
            s += "\n";
        }
        return s;
    }
    public static void main(String[] args){
        In in = new In(args[0]);
        EdgeWeightedGraph G;
        G = new EdgeWeightedGraph(in);
        StdOut.print(G);
    }
}

• 每条边在表中出现两次:和Graph每个顶点出现两次一样,一个Edge在addEdge时,需要给adj[v]和adj[w]同时add
• 平行边:EWG中运行保留权重不一样的平行边
• 自环:EWG中运行存在自环,但edges()未考虑自环

• 使用Edge辅助类的代价:

  • 每个邻接表结点是指向Edge对象的引用,还要冗余信息:每个adj[v]都会保存v
  • 使用对象本身的开销
  • 一个Edge对象需要创建两个引用来指向

4.3.3 最小生成树API和用例(算法4.7)

4.3.4 Prim算法(算法4.7)

4.3.5 Prim算法即时实现(算法4.7)

4.3.6 Kruskal算法(算法4.8)

4.3.7 总结

• 最小生成树算法总结: | 算法 | 空间 | 时间 | | :—-: | :—-: | :—-: | | 延时Prim | E | ElogE | | 即时Prim | V | ElogV | | Kruskal | E | ElogE |