圖中代權(quán)的最小樹的問題如下:
如果N個(gè)城市之間（圖中的頂點(diǎn)）要修公路（圖中的邊）以使所有的城市聯(lián)通，求怎樣修可以使得公路的總長(zhǎng)最小?
以上問題中的N個(gè)城市之間可以用圖中的頂點(diǎn)表示，公路可以圖中的邊表示，公路的長(zhǎng)度用邊長(zhǎng)表示，公路是雙向的。問題就轉(zhuǎn)換為在有N個(gè)頂點(diǎn)中的雙向代權(quán)圖中求得一個(gè)最小樹。這里的代權(quán)指的邊的長(zhǎng)度，這與以前的不代權(quán)的最小樹生成算法有很大的區(qū)別。
算法描述如下：
任選一個(gè)節(jié)點(diǎn)開始，將該節(jié)點(diǎn)標(biāo)志為已訪問過的節(jié)點(diǎn)。也就是最小樹中的節(jié)點(diǎn)。并設(shè)置為當(dāng)前節(jié)點(diǎn)。
1 尋找此訪問節(jié)點(diǎn)的所有的鄰接頂點(diǎn)，將邊置入優(yōu)先隊(duì)列。鄰接頂點(diǎn)不考慮已標(biāo)志為訪問的節(jié)點(diǎn)，因?yàn)樗言诮Y(jié)果中。
2 重復(fù) 步驟1 直到?jīng)]有新的邊被發(fā)現(xiàn)。此時(shí)在所有發(fā)現(xiàn)的邊中找到最小的邊，將其終點(diǎn)頂點(diǎn)標(biāo)志為已訪問，放入最小樹中。并設(shè)置為當(dāng)前節(jié)點(diǎn)
3 重復(fù) 步驟 1，2，直到邊的隊(duì)列中沒有多余的邊，算法結(jié)束。
注意：這里的優(yōu)先級(jí)隊(duì)列是個(gè)修正過的優(yōu)先級(jí)隊(duì)列，每次向該隊(duì)列中加入一條新邊時(shí)后，會(huì)檢查是否有與新邊終點(diǎn)相同的第二條邊的存在，如果有，則刪除邊長(zhǎng)較大的邊。因?yàn)槿绻嬖谶@樣的邊說明，有兩條從已訪問過節(jié)點(diǎn)到相同目標(biāo)節(jié)點(diǎn)的路徑存在，如果這樣的話只用保留最小的那條邊即可。
這里的圖采用Graph 圖－鄰接矩陣法 表示。
算法實(shí)際上是作如下操作：
先準(zhǔn)備好一個(gè)優(yōu)先級(jí)隊(duì)列，里面以邊長(zhǎng)為關(guān)鍵值存放邊，邊的起點(diǎn)表示已被訪問過的節(jié)點(diǎn)，而邊的終點(diǎn)表示未訪問的節(jié)點(diǎn)。將某節(jié)點(diǎn)標(biāo)志為訪問過節(jié)點(diǎn)。開始算法。
尋找該訪問過節(jié)點(diǎn)的所有邊，并記錄邊長(zhǎng)，放入邊優(yōu)先級(jí)隊(duì)列中;
找到所有從已訪問過的節(jié)點(diǎn)到未訪問節(jié)點(diǎn)的邊中的最小邊;
將最小邊連接的頂點(diǎn)設(shè)置為訪問過,重復(fù)以上過程，直到所有節(jié)點(diǎn)都變成已訪問。
主要的類如下：
Edge：記載邊
PriorityQ：修正后的優(yōu)先級(jí)隊(duì)列
Vertex：頂點(diǎn)
Gragh：圖
Gragh.mstw()：最小樹生成算法
Gragh.main()：提供簡(jiǎn)單測(cè)試
代碼如下:
JAVA代碼
1class Edge 
{ //邊：記載起始，與終止節(jié)點(diǎn)的下標(biāo)，以及邊的長(zhǎng)度
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; } //起點(diǎn)
12 int to() { return to; } //終點(diǎn)
13 int length() { return length; } //邊長(zhǎng)
14
}
15
16/** *//**
17 * 修正過的優(yōu)先級(jí)隊(duì)列，邊長(zhǎng)最小的隊(duì)列的頭部，且隊(duì)列中不會(huì)出現(xiàn)到達(dá)同一個(gè)節(jié)點(diǎn)
18 * 的兩條邊，如果添加新邊到隊(duì)列中時(shí)出現(xiàn)這種情況，則隊(duì)列自動(dòng)刪除邊長(zhǎng)較大的邊。
19 */
20class PriorityQ {
21 private Edge[] edges;
22 private int pos = -1;
23 PriorityQ(int size) { //創(chuàng)建指定長(zhǎng)度的優(yōu)先級(jí)隊(duì)列
24 edges = new Edge[size];
25 }
26
27 void add(Edge edge) { //添加新邊到隊(duì)列中
28 assert pos < edges.length;
29 //按照邊長(zhǎng)將新邊插入隊(duì)列中合適的位置
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 //在隊(duì)列中檢查是否有與新邊終點(diǎn)相同的邊，如果有則作修正處理
38 removeDuplicate(edge.to());
39 }
40
41 private void removeDuplicate(int to) { //根據(jù)終點(diǎn)在隊(duì)列中查找重復(fù)的邊，并處理
42 int count = 0; //記錄找到同樣終點(diǎn)的邊的個(gè)數(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 { //頂點(diǎn)類，記載頂點(diǎn)的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 { //無向圖，記錄頂點(diǎn)，頂點(diǎn)之間的邊，以及邊的長(zhǎng)度
75 private Vertex[] vertexs;
76 private int[][] adjMat;
77 private int length = 0;
78 private static final int INFINITY = -1; //表示不存在邊時(shí)的狀態(tài)
79
80 Graph(int size) { //初始化圖的數(shù)據(jù)結(jié)構(gòu)，包括頂點(diǎn)，邊，邊都置為不存在
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) { //添加新的頂點(diǎn)
89 assert length <= vertexs.length;
90 vertexs[length++] = new Vertex(value);
91 }
92
93 void connect(int from, int to, int length) { //頂點(diǎn)之間添加邊，指定邊長(zhǎng)
94 adjMat[from][to] = length;
95 adjMat[to][from] = length;
96 }
97
98 /** *//**
99 * 在鄰接矩陣中，查找指定頂點(diǎn)的未訪問過鄰居頂點(diǎn)
100 * 如果從從起點(diǎn)到終點(diǎn)的邊存在，且沒有標(biāo)志為訪問，則返回終點(diǎn)下標(biāo)。
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為開始的坐標(biāo)
112 assert vertexs[index] != null;
113 Edge[] result = new Edge[length-1]; //生成結(jié)果數(shù)組，邊的數(shù)量為頂點(diǎn)數(shù)量-1
114 PriorityQ q = new PriorityQ(length); //準(zhǔn)備優(yōu)先級(jí)隊(duì)列
115 int pos = -1;
116 vertexs[index].visit(); //將起始頂點(diǎn)標(biāo)志為訪問過的
117 while(true) {
118 //尋找已訪問過的節(jié)點(diǎn)與未訪問過節(jié)點(diǎn)之間的邊，并加入優(yōu)先級(jí)隊(duì)列
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; //如果隊(duì)列中沒有多余的邊，算法結(jié)束
125
126 //在隊(duì)列中找到邊長(zhǎng)最短的邊，將終點(diǎn)節(jié)點(diǎn)標(biāo)志為訪問過，并將此邊從隊(duì)列中刪除
127 result[++pos] = q.remove();
128 index = result[pos].to(); //以新的終點(diǎn)作為起點(diǎn)，準(zhǔn)備下一次迭代
129 vertexs[index].visit();
130 }
131 clean(); //將所有訪問標(biāo)志復(fù)位
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) { //測(cè)試
140 Graph g = new Graph(20);
141 //添加頂點(diǎn)
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 //連接頂點(diǎn)，并指明邊長(zhǎng)
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; //記錄總邊長(zhǎng)
160 for(Edge e: g.mstw(4)) { //以任意頂點(diǎn)開始生成最小樹
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}