圖中代權的最小樹的問題如下:
如果N個城市之間（圖中的頂點）要修公路（圖中的邊）以使所有的城市聯(lián)通，求怎樣修可以使得公路的總長最小?
以上問題中的N個城市之間可以用圖中的頂點表示，公路可以圖中的邊表示，公路的長度用邊長表示，公路是雙向的。問題就轉換為在有N個頂點中的雙向代權圖中求得一個最小樹。這里的代權指的邊的長度，這與以前的不代權的最小樹生成算法有很大的區(qū)別。
算法描述如下：
任選一個節(jié)點開始，將該節(jié)點標志為已訪問過的節(jié)點。也就是最小樹中的節(jié)點。并設置為當前節(jié)點。
1 尋找此訪問節(jié)點的所有的鄰接頂點，將邊置入優(yōu)先隊列。鄰接頂點不考慮已標志為訪問的節(jié)點，因為它已在結果中。
2 重復 步驟1 直到?jīng)]有新的邊被發(fā)現(xiàn)。此時在所有發(fā)現(xiàn)的邊中找到最小的邊，將其終點頂點標志為已訪問，放入最小樹中。并設置為當前節(jié)點
3 重復 步驟 1，2，直到邊的隊列中沒有多余的邊，算法結束。
注意：這里的優(yōu)先級隊列是個修正過的優(yōu)先級隊列，每次向該隊列中加入一條新邊時后，會檢查是否有與新邊終點相同的第二條邊的存在，如果有，則刪除邊長較大的邊。因為如果存在這樣的邊說明，有兩條從已訪問過節(jié)點到相同目標節(jié)點的路徑存在，如果這樣的話只用保留最小的那條邊即可。
這里的圖采用Graph 圖－鄰接矩陣法 表示。
算法實際上是作如下操作：
先準備好一個優(yōu)先級隊列，里面以邊長為關鍵值存放邊，邊的起點表示已被訪問過的節(jié)點，而邊的終點表示未訪問的節(jié)點。將某節(jié)點標志為訪問過節(jié)點。開始算法。
尋找該訪問過節(jié)點的所有邊，并記錄邊長，放入邊優(yōu)先級隊列中;
找到所有從已訪問過的節(jié)點到未訪問節(jié)點的邊中的最小邊;
將最小邊連接的頂點設置為訪問過,重復以上過程，直到所有節(jié)點都變成已訪問。
主要的類如下：
Edge：記載邊
PriorityQ：修正后的優(yōu)先級隊列
Vertex：頂點
Gragh：圖
Gragh.mstw()：最小樹生成算法
Gragh.main()：提供簡單測試
代碼如下:
JAVA代碼
1class Edge 
{ //邊：記載起始，與終止節(jié)點的下標，以及邊的長度
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 * 修正過的優(yōu)先級隊列，邊長最小的隊列的頭部，且隊列中不會出現(xiàn)到達同一個節(jié)點
18 * 的兩條邊，如果添加新邊到隊列中時出現(xiàn)這種情況，則隊列自動刪除邊長較大的邊。
19 */
20class PriorityQ {
21 private Edge[] edges;
22 private int pos = -1;
23 PriorityQ(int size) { //創(chuàng)建指定長度的優(yōu)先級隊列
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) { //根據(jù)終點在隊列中查找重復的邊，并處理
42 int count = 0; //記錄找到同樣終點的邊的個數(shù)
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; //表示不存在邊時的狀態(tài)
79
80 Graph(int size) { //初始化圖的數(shù)據(jù)結構，包括頂點，邊，邊都置為不存在
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]; //生成結果數(shù)組，邊的數(shù)量為頂點數(shù)量-1
114 PriorityQ q = new PriorityQ(length); //準備優(yōu)先級隊列
115 int pos = -1;
116 vertexs[index].visit(); //將起始頂點標志為訪問過的
117 while(true) {
118 //尋找已訪問過的節(jié)點與未訪問過節(jié)點之間的邊，并加入優(yōu)先級隊列
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 //在隊列中找到邊長最短的邊，將終點節(jié)點標志為訪問過，并將此邊從隊列中刪除
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}