加權(quán)圖是一種為每條邊關(guān)聯(lián)一個(gè)權(quán)值或是成本的圖模型。而最小生成樹(shù)與之密切相關(guān)。
定義 圖的生成樹(shù)是它的一棵含有其所有頂點(diǎn)的無(wú)環(huán)連通子圖。一幅加權(quán)圖的最小生成樹(shù)是它的一棵權(quán)值最小的生成樹(shù)。
** 切分定理 **
定義 圖的一種切分是將圖的所有頂點(diǎn)分為兩個(gè)非空且不重疊的兩個(gè)集合。橫切邊是一條連接兩個(gè)屬于不同集合的頂點(diǎn)的邊。
通常，我們通過(guò)指定一個(gè)頂點(diǎn)集并隱式的認(rèn)為它的補(bǔ)集為另一個(gè)頂點(diǎn)集來(lái)指定一個(gè)切分。這樣，一條橫切邊就是連接該集合的一個(gè)頂點(diǎn)和不在該集合的另一個(gè)頂點(diǎn)的一條邊。
切分定理。 在一幅加權(quán)圖中，給定任意的切分，它的橫切邊中的權(quán)重最小者必定屬于圖的最小生成樹(shù)。
貪心算法
切分定理是解決最小生成樹(shù)問(wèn)題的所有算法的基礎(chǔ)。更確切的說(shuō)，這些算法都是一種貪心算法的特殊情況：使用切分定理找到最小生成樹(shù)的一條邊，不斷重復(fù)找到最小生成樹(shù)的所有邊。這些算法相互之間的不同之處在于保存切分和判定權(quán)重最小的橫切邊的方式，但他們都是以下性質(zhì)的特殊情況。
最小生成樹(shù)的貪心算法。 下面這種方法會(huì)將含有v個(gè)頂點(diǎn)的任意加權(quán)連通圖中屬于最小生成樹(shù)的標(biāo)記為黑色：初始狀態(tài)下邊均為灰色，找到一種切分，它產(chǎn)生的橫切邊均不為黑色，將它權(quán)重最小的橫切邊標(biāo)記為黑色。反復(fù)，直到找到了V-1條黑色的邊。
加權(quán)無(wú)向圖的數(shù)據(jù)結(jié)構(gòu)
//加權(quán)邊的API
public class Edge implements Comparable<Edge>
Edge(int v, int w, doouble weight) //用于初始化構(gòu)造函數(shù)
double weight() //邊的權(quán)重
int either() //邊兩端的頂點(diǎn)之一
int other(int v) //另一個(gè)頂點(diǎn)
int compareTo(Edge that) //將這條邊與that作比較
String toString() //對(duì)象的字符串表示
//加權(quán)無(wú)向圖的API
public class EdgeWeightedGraph
EdgeWeightedGraph(int V) //創(chuàng)建一幅含有V個(gè)頂點(diǎn)的空?qǐng)D
EdgeWeightedGraph(In in) //從輸入流讀取圖
int V() //圖的頂點(diǎn)數(shù)
int E() //圖的邊數(shù)
void addEdge(Edge e) //向圖中添加一條邊e
Iterable<Edge> adj(int v) //和v相關(guān)聯(lián)的所有邊
Iterable<Edge> edges() //圖的所有邊
string toString() //對(duì)象的字符串表示
為了簡(jiǎn)潔，用一對(duì)int值和一個(gè)double值來(lái)表示每個(gè)Edge對(duì)象。實(shí)際的數(shù)據(jù)結(jié)構(gòu)是一個(gè)鏈表，其中每個(gè)元素都是一個(gè)指向含有這些元素的對(duì)象的指針。雖然每個(gè)Edge對(duì)象都有兩個(gè)引用（每個(gè)頂點(diǎn)的鏈表中都有一個(gè)），但是每條邊所對(duì)應(yīng)的Edge只有一個(gè)。
帶權(quán)重的邊的數(shù)據(jù)類型
public class Edge implements Comparable<Edge>{
private final int v; //頂點(diǎn)之一
private fianl int w; //另一個(gè)頂點(diǎn)
private final double weight; //邊的權(quán)重
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);
}
加權(quán)無(wú)向邊的數(shù)據(jù)類型
public class EdgeWeightedGraph{
private final int V; //頂點(diǎn)邊數(shù)
private int E; //邊的總數(shù)
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;
}
}
** 最小生成樹(shù)的API與測(cè)試用例**
由于圖G的最小生成樹(shù)是G的一幅子圖并且同時(shí)也是一棵樹(shù)，因此我們有很多選擇：
1.一組邊的列表;
2.一幅加權(quán)無(wú)向圖;
3.一個(gè)以頂點(diǎn)為索引且含有父結(jié)點(diǎn)鏈接的數(shù)組;
最小生成樹(shù)的API：
public class MST
MST (EdgeWeightedGraph G) //構(gòu)造函數(shù)
Iterable<Edge> edges() //最小生成樹(shù)的所有邊
double weight() //最小生成樹(shù)的權(quán)重
測(cè)試用例：
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());
}
