学步园

图中代权的最小树的问题如下:

如果N个城市之间（图中的顶点）要修公路（图中的边）以使所有的城市联通，求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示，公路可以图中的边表示，公路的长度用边长表示，公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度，这与以前的不代权的最小树生成算法有很大的区别。

算法描述如下：

    任选一个节点开始，将该节点标志为已访问过的节点。也就是最小树中的节点。并设置为当前节点。
    1 寻找此访问节点的所有的邻接顶点，将边置入优先队列。邻接顶点不考虑已标志为访问的节点，因为它已在结果中。
    2 重复 步骤1 直到没有新的边被发现。此时在所有发现的边中找到最小的边，将其终点顶点标志为已访问，放入最小树中。并设置为当前节点
    3 重复 步骤 1，2，直到边的队列中没有多余的边，算法结束。

    注意：这里的优先级队列是个修正过的优先级队列，每次向该队列中加入一条新边时后，会检查是否有与新边终点相同的第二条边的存在，如果有，则删除边长较大的边。因为如果存在这样的边说明，有两条从已访问过节点到相同目标节点的路径存在，如果这样的话只用保留最小的那条边即可。

这里的图采用Graph 图－邻接矩阵法 表示。

算法实际上是作如下操作：

    先准备好一个优先级队列，里面以边长为关键值存放边，边的起点表示已被访问过的节点，而边的终点表示未访问的节点。将某节点标志为访问过节点。开始算法。
    寻找该访问过节点的所有边，并记录边长，放入边优先级队列中;
    找到所有从已访问过的节点到未访问节点的边中的最小边;
    将最小边连接的顶点设置为访问过,重复以上过程，直到所有节点都变成已访问。

主要的类如下：

    Edge：记载边

    PriorityQ：修正后的优先级队列

    Vertex：顶点

    Gragh：图

        Gragh.mstw()：最小树生成算法

        Gragh.main()：提供简单测试

代码如下:

  1class Edge {    //边：记载起始，与终止节点的下标，以及边的长度
  2    private int from;
  3    private int to;
  4    private int length;
  5    Edge(int from, int to, int length) {
  6        this.from = from;
  7        this.to = to;
  8        this.length = length;
  9    }
 10
 11    int from() { return from; }    //起点
 12    int to() { return to; }    //终点
 13    int length() { return length; }    //边长
 14}
 15
 16/**
 17 * 修正过的优先级队列，边长最小的队列的头部，且队列中不会出现到达同一个节点
 18 * 的两条边，如果添加新边到队列中时出现这种情况，则队列自动删除边长较大的边。
 19 */
 20class PriorityQ {    
 21    private Edge[] edges;
 22    private int pos = -1;
 23    PriorityQ(int size) {    //创建指定长度的优先级队列
 24        edges = new Edge[size];
 25    }
 26
 27    void add(Edge edge) {    //添加新边到队列中
 28        assert pos < edges.length;
 29        //按照边长将新边插入队列中合适的位置
 30        int index = ++pos;
 31        while(index > 0 && edges[index-1].length() < edge.length()) {
 32            edges[index] = edges[index-1];
 33            index--;    
 34        }
 35        edges[index] = edge;    
 36
 37        //在队列中检查是否有与新边终点相同的边，如果有则作修正处理
 38        removeDuplicate(edge.to());        
 39    }
 40
 41    private void removeDuplicate(int to) {    //根据终点在队列中查找重复的边，并处理
 42        int count = 0;    //记录找到同样终点的边的个数
 43        for(int index=pos; index>-1; index--) {
 44            if(edges[index].to() == to) count++;    
 45            if(count == 2) {    //将第二次找到的边作删除处理
 46                for(int i=index; i<pos; i++) edges[i] = edges[i+1];
 47                pos--;
 48                return;
 49            }
 50        }
 51    }
 52
 53    Edge remove() {    //移出并返回最小的边
 54        return edges[pos--];    
 55    }
 56
 57    boolean isEmpty() { return pos == -1; }
 58}
 59
 60class Vertex {    //顶点类，记载顶点的value，并可以记录是否访问过
 61    private Object value;
 62    private boolean isVisited;
 63    Vertex(Object value) {
 64        this.value = value;
 65    }
 66
 67    void visit() { isVisited = true; }
 68    void clean() {    isVisited = false; }
 69    boolean isVisited() { return isVisited; }
 70    Object value() { return value; }
 71    @Override public String toString() { return "" + value; }
 72}
 73
 74class Graph {    //无向图，记录顶点，顶点之间的边，以及边的长度
 75    private Vertex[] vertexs;
 76    private int[][] adjMat;
 77    private int length = 0;
 78    private static final int INFINITY = -1;    //表示不存在边时的状态
 79
 80    Graph(int size) {    //初始化图的数据结构，包括顶点，边，边都置为不存在
 81        vertexs = new Vertex[size];    
 82        adjMat = new int[size][size];
 83        for(int i=0; i<size; i++) 
 84            for(int j=0; j<size; j++)
 85                adjMat[i][j] = INFINITY;
 86    }
 87
 88    void add(Object value) {    //添加新的顶点
 89        assert length <= vertexs.length;
 90        vertexs[length++] = new Vertex(value);
 91    }
 92
 93    void connect(int from, int to, int length) {    //顶点之间添加边，指定边长
 94        adjMat[from][to] = length;
 95        adjMat[to][from] = length;
 96    }
 97
 98    /**
 99     * 在邻接矩阵中，查找指定顶点的未访问过邻居顶点
100     * 如果从从起点到终点的边存在，且没有标志为访问，则返回终点下标。
101     * @param offset 指定开始查找的列
102     * @param index    指定查找的行
103     */
104    int findNeighbor(int index,int offset) {    //
105        for(int i=offset; i<length; i++) {
106            if(adjMat[index][i] != INFINITY && !vertexs[i].isVisited()) return i;
107        }
108        return -1;
109    }
110
111    Edge[] mstw(int index) {    //最小树生成算法，index为开始的坐标
112        assert vertexs[index] != null;
113        Edge[] result = new Edge[length-1]; //生成结果数组，边的数量为顶点数量-1
114        PriorityQ q = new PriorityQ(length);    //准备优先级队列
115        int pos = -1;
116        vertexs[index].visit();    //将起始顶点标志为访问过的
117        while(true) {
118            //寻找已访问过的节点与未访问过节点之间的边，并加入优先级队列
119            int i = -1;
120            while((i = findNeighbor(index,i+1)) != -1) {    
121                Edge e = new Edge(index,i,adjMat[index][i]);
122                q.add(e);    
123            }
124            if(q.isEmpty()) break;    //如果队列中没有多余的边，算法结束
125            
126            //在队列中找到边长最短的边，将终点节点标志为访问过，并将此边从队列中删除
127            result[++pos] = q.remove();    
128            index = result[pos].to();    //以新的终点作为起点，准备下一次迭代
129            vertexs[index].visit();
130        }
131        clean();    //将所有访问标志复位
132        return result;
133    }
134
135    void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }
136
137    Object get(int index) { return vertexs[index]; }
138
139    public static void main(String[] args) {    //测试
140        Graph g = new Graph(20);
141        //添加顶点
142        g.add('a');
143        g.add('b');
144        g.add('c');
145        g.add('d');
146        g.add('e');
147        g.add('f');
148        //连接顶点，并指明边长
149        g.connect(0,1,6);
150        g.connect(0,3,4);
151        g.connect(1,2,10);
152        g.connect(1,3,7);
153        g.connect(1,4,7);
154        g.connect(2,3,8);
155        g.connect(2,4,5);
156        g.connect(2,5,6);
157        g.connect(3,4,12);
158        g.connect(4,5,7);
159        int sum = 0;    //记录总边长
160        for(Edge e: g.mstw(4)) {    //以任意顶点开始生成最小树
161            System.out.println(g.get(e.from()) + " -- " + g.get(e.to()) + " : " + e.length());
162            sum += e.length();
163        }
164        System.out.println(sum);
165    }
166}