图中代权的最小树的问题如下:
如果N个城市之间（图中的顶点）要修公路（图中的边）以使所有的城市联通，求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示，公路可以图中的边表示，公路的长度用边长表示，公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度，这与以前的不代权的最小树生成算法有很大的区别。
算法描述如下：
任选一个节点开始，将该节点标志为已访问过的节点。也就是最小树中的节点。并设置为当前节点。
1 寻找此访问节点的所有的邻接顶点，将边置入优先队列。邻接顶点不考虑已标志为访问的节点，因为它已在结果中。
2 重复 步骤1 直到没有新的边被发现。此时在所有发现的边中找到最小的边，将其终点顶点标志为已访问，放入最小树中。并设置为当前节点
3 重复 步骤 1，2，直到边的队列中没有多余的边，算法结束。
注意：这里的优先级队列是个修正过的优先级队列，每次向该队列中加入一条新边时后，会检查是否有与新边终点相同的第二条边的存在，如果有，则删除边长较大的边。因为如果存在这样的边说明，有两条从已访问过节点到相同目标节点的路径存在，如果这样的话只用保留最小的那条边即可。
这里的图采用Graph 图－邻接矩阵法 表示。
算法实际上是作如下操作：
先准备好一个优先级队列，里面以边长为关键值存放边，边的起点表示已被访问过的节点，而边的终点表示未访问的节点。将某节点标志为访问过节点。开始算法。
寻找该访问过节点的所有边，并记录边长，放入边优先级队列中;
找到所有从已访问过的节点到未访问节点的边中的最小边;
将最小边连接的顶点设置为访问过,重复以上过程，直到所有节点都变成已访问。
主要的类如下：
Edge：记载边
PriorityQ：修正后的优先级队列
Vertex：顶点
Gragh：图
Gragh.mstw()：最小树生成算法
Gragh.main()：提供简单测试
代码如下:
JAVA代码
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}