最小生成树（一）

加权图是一种为每条边关联一个权值或是成本的图模型。而最小生成树与之密切相关。

定义图的生成树是它的一棵含有其所有顶点的无环连通子图。一幅加权图的最小生成树是它的一棵权值最小的生成树。

** 切分定理 **

定义图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边。

通常，我们通过指定一个顶点集并隐式的认为它的补集为另一个顶点集来指定一个切分。这样，一条横切边就是连接该集合的一个顶点和不在该集合的另一个顶点的一条边。

切分定理。在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必定属于图的最小生成树。

贪心算法
切分定理是解决最小生成树问题的所有算法的基础。更确切的说，这些算法都是一种贪心算法的特殊情况：使用切分定理找到最小生成树的一条边，不断重复找到最小生成树的所有边。这些算法相互之间的不同之处在于保存切分和判定权重最小的横切边的方式，但他们都是以下性质的特殊情况。

最小生成树的贪心算法。下面这种方法会将含有v个顶点的任意加权连通图中属于最小生成树的标记为黑色：初始状态下边均为灰色，找到一种切分，它产生的横切边均不为黑色，将它权重最小的横切边标记为黑色。反复，直到找到了V-1条黑色的边。

加权无向图的数据结构

//加权边的API    
public class Edge implements Comparable<Edge>
             Edge(int v, int w, doouble weight)          //用于初始化构造函数
      double weight()                      //边的权重
         int either()                    //边两端的顶点之一
         int other(int v)                //另一个顶点
         int compareTo(Edge that)    //将这条边与that作比较
      String toString()                //对象的字符串表示

//加权无向图的API
public class EdgeWeightedGraph
             EdgeWeightedGraph(int V)        //创建一幅含有V个顶点的空图
             EdgeWeightedGraph(In in)        //从输入流读取图
         int V()                        //图的顶点数
         int E()                        //图的边数
        void addEdge(Edge e)   //向图中添加一条边e
Iterable<Edge> adj(int v)        //和v相关联的所有边
Iterable<Edge> edges()          //图的所有边
        string toString()            //对象的字符串表示

为了简洁，用一对int值和一个double值来表示每个Edge对象。实际的数据结构是一个链表，其中每个元素都是一个指向含有这些元素的对象的指针。虽然每个Edge对象都有两个引用（每个顶点的链表中都有一个），但是每条边所对应的Edge只有一个。

带权重的边的数据类型

public class Edge implements Comparable<Edge>{
    private final int v;          //顶点之一
    private fianl 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("%2d-%2d %.2f",v,w,weight);
    }

加权无向边的数据类型

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<Edge>();
    }
    public EdgeWeightedGraph(In in)

    public int V() {  return V;}
    public int E() {  return E;}
    public void addEdge(Edge e){
        int v = e.either(), w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }
    public Iterable<Edge> adj(int v){
        return adj[v];  
    }
    public Iterable<Edge> edges(){
        Bag<Edge> b = new Bag<Edge>();
        for( int v=0; v<W; v++)
            for(Edge e: adj[v])
                if( e.other(v) > v) b.add(e);
        return b;
    }
}

** 最小生成树的API与测试用例**
由于图G的最小生成树是G的一幅子图并且同时也是一棵树，因此我们有很多选择：
1.一组边的列表;
2.一幅加权无向图;
3.一个以顶点为索引且含有父结点链接的数组;
最小生成树的API：

public class MST
             MST (EdgeWeightedGraph G)      //构造函数
    Iterable<Edge> edges()              //最小生成树的所有边
      double weight()                     //最小生成树的权重

测试用例：

public static void main(String[] args){
    In in = new In(args[0]);
    EdgeWeightedGraph G;
    G = new EdgeWeightedGraph(in);
    MST mst = new MST(G);
    for( Edge e: mst.edges())
        StdOut.println(e);
    StdOut.println(mst.weight());
}

最小生成树（一）

推荐阅读更多精彩内容