最小生成树
有权图
有权图是指在无权图的基础上，每一条边都有一个数值，代表两个结点之间有一定的数值关系，比如图用来表示路网时，权值可以表示两点之间的距离，到达彼此所需要的时间等。
有权图的邻接矩阵表达见下图:
有权图的邻接表表达见下图: s 
邻接表每个节点后面存储两个信息:to表示和它相邻的节点的索引，w表示对应的边的权值.所以可以将这两个信息封装为Edge属性，它包含to和w属性。
当然要注意一点，邻接矩阵中依然用了传统的二维数组来存储，为了统一图的接口，也可以将a[i][j]位置存储为Edge格式。
这里就直接先写java代码了
创建WeightedGraph.java接口:
public interface WeightedGraph<Weight extends Number & Comparable> {
public int V(); //获取图的顶点数
public int E(); //获取图的边数
public void addEdge(Edge<Weight> e); //在v和w两个顶点间添加一条边
boolean hasEdge( int v , int w);//查看v和w两个顶点间是否有边
void show();//打印图
public Iterable<Edge<Weight>> adj(int v); //获取与v顶点连接的所有边
}
为了实现有权图，先编写一个Edge.java类:
//边
public class Edge<Weight extends Number & Comparable> implements Comparable<Edge> {
private int a,b; //边的两个端点
private Weight weight; //边的权值
public Edge(int a, int b , Weight weight){
this.a = a ;
this.b = b ;
this.weight = weight;
}
public Edge(Edge<Weight> e){
this.a = e.a;
this.b = e.b;
this.weight = e.weight;
}
public int v() {return a;} //返回第一个顶点
public int w() {return b;} //返回第二个顶点
public Weight wt() {return weight;} // 返回权值
//给定一个顶点，返回另一个顶点
public int other(int x){
if( x == a || x == b){
return x == a ? b : a;
}else
throw new IllegalArgumentException("x is not correct");
}
//输出边的信息
public String toString(){
return "" + a + "-" + b + ": " + weight;
}
@Override
public int compareTo(Edge that) {
if(weight.compareTo(that.wt()) < 0)
return -1;
else if(weight.compareTo(that.wt()) > 0)
return +1;
else
return 0;
}
}
在DenseGraph.java的基础上修改，创建DenseGraph.java:
import java.util.Vector;
public class DenseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph {
private int n; //节点数
private int m; //边数
private boolean directed; // 是否为有向图
private Edge<Weight>[][] g; //图的具体数据，用二维数组表达
//构造函数
public DenseWeightedGraph( int n , boolean directed){
if(n < 0)
throw new IllegalArgumentException("the value of n should be >= 0.");
this.n = n;
this.m = 0 ;//初始化时没有任何边
this.directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为null, 表示没有任和边
// false为boolean型变量的默认值
g = new Edge[n][n];
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ;j ++)
g[i][j] = null;
}
//返回节点个数
@Override
public int V() {
return n;
}
//返回边数
@Override
public int E() {
return m;
}
//向图中添加一条边
@Override
public void addEdge(Edge e) {
if(!(e.v() >= 0 && e.v() < n))
throw new IllegalArgumentException("you should type v >= 0 && v < n");
if(!(e.w() >= 0 && e.w() < n))
throw new IllegalArgumentException("you should type w >= 0 && w < n");
if(hasEdge(e.v(),e.w()))
return;
g[e.v()][e.w()] = new Edge(e);
if(e.v() != e.w() && !directed)
g[e.w()][e.v()] = new Edge(e.w(),e.v(),e.wt());
m ++;
}
//判断图中是否有v到w的边
@Override
public boolean hasEdge(int v, int w) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(w >= 0 && w < n))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
return g[v][w] != null;
}
//打印显示图的信息
@Override
public void show() {
for(int i = 0 ; i < n ; i ++){
for( int j = 0 ; j < n ; j ++)
if( g[i][j] != null)
System.out.println(g[i][j].wt()+"\t");
else
System.out.println("NULL\t");
System.out.println();
}
}
//返回图中v顶点的所有邻边
//由于java使用引用机制，返回一个Vector不会带来额外开销
@Override
public Iterable<Edge<Weight>> adj(int v) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
Vector<Edge<Weight>> adjV = new Vector<Edge<Weight>>();
for(int i = 0 ; i < n ; i++)
if(g[v][i] != null)
adjV.add(g[v][i]);
return adjV;
}
}
同样的修改SparseGraph.java后得到SparseWeightedGraph.java：
import java.util.Vector;
public class SparseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph {
private int n; //节点数
private int m; //边数
private boolean directed; //是否为有向图
private Vector<Edge<Weight>>[] g; //图的具体数据
//构造函数
public SparseWeightedGraph(int n , boolean directed){
if(n < 0)
throw new IllegalArgumentException("the value of n should be >= 0.");
this.n = n;
this.m = 0;
this.directed = directed;
//g初始化为n个空的vector,表示每一个g[i]都为空，即没有任何边
g = (Vector<Edge<Weight>>[]) new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Edge<Weight>>();
}
//返回节点个数
@Override
public int V() {
return n;
}
//返回边数
@Override
public int E() {
return m;
}
//向图中添加一条边
@Override
public void addEdge(Edge e) {
if(!(e.v() >= 0 && e.v() < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(e.w() >= 0 && e.w() < n))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
g[e.v()].add(new Edge<>(e));
if(e.v() != e.w() && !directed) //如果不是自环边，并且它是无向图，则创建w到v的边
g[e.w()].add(new Edge(e.w(),e.v(),e.wt()));
m ++;
}
//验证图中是否有v到w的边
@Override
public boolean hasEdge(int v, int w) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(w >= 0 && w < n))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
for(int i = 0 ; i < g[v].size() ; i++)
if( g[v].elementAt(i).other(v) == w)
return true;
return false;
}
//显示图的信息
@Override
public void show() {
for(int i = 0; i < n ; i ++){
System.out.printf("vertex %d :\t",i);
for(int j = 0 ; j < g[i].size() ; j++){
Edge e = g[i].elementAt(j);
System.out.print("( to:" + e.other(i) + ",wt:" + e.wt() + ")\t");
}
System.out.println();
}
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销,
@Override
public Iterable<Edge<Weight>> adj(int v) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
return g[v];
}
}
修改ReadGraph.java后得到ReadWeightedGraph:
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class ReadWeightedGraph {
private Scanner scanner;
public ReadWeightedGraph(WeightedGraph<Double> graph , String filename){
readFile(filename);
try{
int V = scanner.nextInt();
if(V < 0 )
throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative");
assert V == graph.V();
int E = scanner.nextInt();
if(E < 0 )
throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");
for(int i = 0 ; i < E ; i ++){
int v = scanner.nextInt();
int w = scanner.nextInt();
Double weight = scanner.nextDouble(); //读取权值
if(!(v >= 0 && v < V))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(w >= 0 && w < V))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
graph.addEdge(new Edge<Double>(v,w,weight) );
}
}catch (InputMismatchException e){
String token = scanner.next();
throw new InputMismatchException("attempts to read an 'int' value from input stream,but the next token is \""+token +"\"");
}catch(NoSuchElementException e){
throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available");
}
}
private void readFile(String filename){
if(filename == null)
throw new IllegalArgumentException("filename should not be null!");
try {
File file = new File(filename);
if (file.exists()) {
FileInputStream fis = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
scanner.useLocale(Locale.ENGLISH);
}else
throw new IllegalArgumentException(filename + "doesn't exists.");
}catch (IOException ex){
throw new IllegalArgumentException("Could not open " + filename,ex);
}
}
}
测试文件testG1.txt:
8 16
4 5 .35
4 7 .37
5 7 .28
0 7 .16
1 5 .32
0 4 .38
2 3 .17
1 7 .19
0 2 .26
1 2 .36
1 3 .29
2 7 .34
6 2 .40
3 6 .52
6 0 .58
6 4 .93
在Main.java中进行测试:
public class Main {
// 测试通过文件读取图的信息
public static void main(String[] args) {
// 使用两种图的存储方式读取testG1.txt文件
String filename = "testG1.txt";
SparseWeightedGraph<Double> g1 = new SparseWeightedGraph<Double>(8, false);
ReadWeightedGraph readGraph1 = new ReadWeightedGraph(g1, filename);
System.out.println("test G1 in Sparse Weighted Graph:");
g1.show();
System.out.println();
DenseWeightedGraph<Double> g2 = new DenseWeightedGraph<Double>(8, false);
ReadWeightedGraph readGraph2 = new ReadWeightedGraph(g2 , filename );
System.out.println("test G1 in Dense Graph:");
g2.show();
System.out.println();
}
}
最小生成树问题
算法（第四版）中的定义： 最小生成树。给定一个加权无向图，找到它的一棵最小生成树（Minimum Span Tree）。
如果一个图有v个节点，那么就应该有v-1条边连接这V个节点，这就是这个图的生成树。不仅如此，这v-1条边连接了所有的v个节点，这v-1条边的权值相加也是最小的，如何找到这个生成树，就是最小生成树问题。
一些约定
这里在计算最小生成树的过程中会出现各种特殊情况，所以为了行文流畅，进行约定：
- 只考虑连通图
- 针对带权无向图
- 所有边的权重都各不相同
所以在进行最小生成树相关算法的过程中要找V-1条边，连接V个顶点使得其总权值最小。
切分定理 - Cut Property
把图中的结点分为两个部分，成为一个切分(Cut).
如下图就是一个切分:
如果一个边的两个端点，属于切分(Cut)不同的两边，这个边称为横切边(Crossing Edge).
如下图的蓝色线条就是横切边:
切分定理的定义： 在一副加权图中，给定任意切分，横切边中权值最小的边必然属于图的最小生成树。
例如上图中的权重为0.4的边肯定是最小生成树的一条边: 
算法(第四版)中的证明:
今e为权重最小的横切边，T为图的最小生成树。我们采用反证法:假设T不包含e。那么如果将e加入T，得到的图必然含有一条经过e的环，且这个环至少含有另一条横切边——设为f，f的权重必然大于e(因为e的权重是最小的且图中所有边的权重均不同)。那么我们删掉f而保留e就可以得到一棵权重更小的生成树。这和我们的假设T矛盾。
在假设所有的边的权重均不相同的前提下，每幅连通图都只有一棵唯一的最小生成树，切分定理也表明了对于每一种切分，权重最小的横切边必然属于最小生成树。
切分定理是解决最小生成树问题的所有算法的基础。更确切的说，这些算法都是一种贪心算法的特殊情况:使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。这些算法相互之间的不同之处在于保存切分和判定权重最小的横切边的方式。
Lazy Prim算法
首先将一个起始节点作为切分的一部分，这里从0节点开始。将0节点作为切分的一部分，剩下的节点作为切分的另一部分。每一次找到横切边中权值最小的边。这里可以使用最小堆，将横切边放入最小堆中，作为最小生成树所包含的边的候选。这些边进入堆后，下一步只需拿出最小堆中的最短边就可以了。
这一步找出的是0-7:0.16权值为0.16的边，它一定属于最小生成树。
第二步，确定了0-7这条边为最小生成树的一条边，而结点7没有被访问过，此时就可以将结点7加入到红色节点部分，这样就形成了一个新的切分。这个新的切分就和另一部分切分形成了新的横切边。
然后将这些新的横切边推入最小堆，然后在最小堆中选出权值最小的边1-7:0.19。
第三步，确定了1-7为最小生成树的一条边，而节点1没有被访问过，此时将结点1加入到红色结点部分，这样又形成了一个新的切分。也相应的和另一部分切分形成了新的横切边。将这些新的横切边加入到最小堆。
接着看在候选的横切边中，最短的边为0-2:0.26的边。
第四步，确定了0-2为最小生成树的一条边，而结点2没有被访问过，所以将结点2加入红色结点部分，这样就又形成一个新的切分。又有新的边成为了横切边。将他们加入到最小堆中。
此时需要注意，将结点2加入到红色部分后，最小堆中蓝色的部分中，边2-7:0.34和边1-2:0.36，实际上已经不是横切边了，所以这两条边不应该成为最小生成树的边的候选了。所以这里体现出Lazy Prim算法的”懒惰”性，当前这两条边虽然不可能成为最小生成树的候选边，但是这里不需要着急将其剔除，先将其保留在最小堆中，当拿出这两条边时，发现这两条边不是横切边时，再将这两条边剔除。
接着在最小堆中寻找最小的边，最短边为2-3:0.17的边.
第五步，确定了2-3为最小生成树的一条边，而结点3没有被访问过，所以将结点3加入到红色结点部分，形成新的切分后，将新的横切边加入到最小堆中。
接着最小堆中的最小边应该是5-7:0.28的边。
第六步，确定了5-7为最小生成树的一条边，而结点5没有被访问过，所以将结点5加入到红色部分，形成新的切分并将新的横切边加入到最小堆中。
接着看在最小堆中，最小的边为1-3:0.29的边，当将其拿出后发现，结点1和结点3都是红色的结点，即这条边不是一条横切边（只有横切边中的最小边才是最小生成树的边），所以将其拿出后剔除。接着看在最小堆中的最短边为1-5:0.32的边，拿出后发现结点1和结点5都是红色的结点，所以也要将其剔除。接着看剩下的最小堆中的最短边为2-7:0.34，也不满足横切边的性质，剔除。 接着看剩下的最小堆中的最短边为4-5:0.35，满足横切边的性质，所以将这条边作为最小生成树的边。
第七步，确定了5-4为最小生成树的一条边，由于结点4没有被访问过，所以将结点4加入到红色部分，行成新的切分并将新的横切边4-6:0.93加入到最小堆中。
然后在最小堆中找最短的边，为1-2:0.36这条边，但是它不是横切边，将其剔除。接着最小堆中最短的边为4-7:0.37，它不是横切边，将其剔除。继续找最小堆中最短边为0-4:0.38，不是横切边，将其剔除。 继续找最小堆中的最短边为2-6:0.40，它是横切边，将其作为最小生成树的边。
由于结点6没有被访问过，将其加入到红色部分。这时所有节点都在红色部分，程序至此就可以结束。
如果以最小堆中的边为空作为判断依据的话，那么依然可以拿出最小堆中的最小边进行判断，此时所有的边都不是横切边，将剩下的边判断完后，程序结束。
此时就用Lazy Prim算法获得了最小生成树。
Lazy Prim算法代码
见附录1
Prim算法的优化
pq.extractMin()操作的时间复杂度为O(logE),因为pq中最多承载E条边。 visit()操作时，遍历节点的所有临边，合在一起也是O(E)，如果是邻接矩阵就是O(V^2)，在稠密图的邻接矩阵中O(V^2)和O(E)是一个级别的。同时其中有个add()操作，它是O(logE)级别的。
所以，Lazy Prim算法的时间复杂度为O(ElogE).
通过优化，Prim算法的时间复杂度可以改进为O(ElogV).
Lazy Prim算法的一个问题就是，所有的边都要进入最小堆，随着切分的进行，很多已经不是横切边的边仍在最小堆中。另一问题是，虽然有很多横切边，但我们只关注最短的那个横切边，尤其是和一个节点相连的很多横切边，其实只需考虑和这个点相连的最短的横切边就可以了。
基于这个思想，需要维护一个数据结构——存储和每个节点相连的那个最短的横切边。在不断增加红色节点改变切分的过程中，只要不断更新和每个节点相连的最短的横切边就可以了。即这个数据结构要满足：①它能取到最小值②能够供我们更新。所以需要使用IndexMinHeap.
第一步: 以0作为起点开始，由于最小生成树有V-1个边，而IndexMinHeap有V个空间，所以肯定有一个节点不需要存储任何东西。就将初始结点作为不需要存储东西的节点。此时有了初始节点后，相当于有了切分，这时，这个节点的所有临边都是横切边，这种情况下，就将这些横切边加入到IndexMinHeap中。 此时，和2相连的横切边，最小权值是0.26;和4相连的横切边，最小权值是0.38;和6相连的横切边，最小权值是0.58;和7相连的横切边，最小权值是0.16.
这时，从IndexMinHeap中找出权值最小的一条边，根据切分定理，一定是最小生成树的边，即0.16这条边。这时节点7加入红色部分。
第二步，由于结点7加入了红色部分。要考虑更多的横切边，这时遍历结点7的临边。先看1-7，此时IndexMinHeap中没有和1相连的横切边权值最小的边，所以IndexMinHeap中1的值更新为0.19;再看2-7，其值为0.34，而IndexMinHeap中和2相连的横切边权值最小的是0-2:0.26，所以2-7肯定不会是最小生成树中的一条边，可以直接剔除；接着看4-7，这个边的权值为0.37,它小于当前IndexMinHeap中存储的0.38，所以将4-7:0.37更新到最小索引堆中，与此同时，意味着将0-4:0.38这条边丢弃，因为这条边不可能会是最小生成树的边;最后，看5-7，这个边的权值为0.28，当前IndexMinHeap和5相连的边还没有，所以将其放入IndexMinHeap索引为5的位置中。这时候就完成了visit(7)操作。
然后从最小索引堆IndexMinHeap中找出权值最小的边，即和1相连的1-7:0.19这条边，可以确定它属于最小生成树。因此结点1也可以加入红色部分
第三步，看和结点1相邻的所有边。首先是1-2:0.36，在IndexMinHeap中索引为2的位置其值为0.26，所以1-2不是最小生成树的边；接着看1-5:0.32，但是在IndexMinHeap中和5相连的横切边最小的值为0.28，所以它也不是最小生成树的边;最后看1-3:0.29，由于IndexMinHeap中没有和3相连的横切边，将其放入IndexMinHeap中。
然后从最小索引堆中找出权值最小的边，即和2相连的0-2:0.26这条边，可以确定它属于最小生成树。与此同时结点2加入红色部分。
第四步，看和结点2相邻的所有边。这里注意2-7和1-2不是横切边，所以不用再看了；然后看2-3:0.17，此时最小索引堆中索引为3的位置的值为0.29，所以将其更新为0.17,同时0.29这条边可以剔除不在考虑;接着看2-6:0.40，此时最小索引堆中的索引为6的位置的值为0.58，所以将其更新为0.40，同时0.58这条边可以剔除不在考虑了.
然后从最小索引堆中取出权值最小的边，即和3相连的0.17这条边，根据切分定理，其一定属于最小生成树。同时，将接点3加入红色部分。
第五步，看和接点3相邻的所有边。1-3不是横切边，所以不用看；剩下一条3-6:0.52,其值0.52大于最小索引堆索引为6处的0.40，所以这条边剔除不再考虑。
然后从最小索引堆中找出权值最小的边，即和5相连的0.28这条边，它一定是最小生成树的边。同时将结点5加入红色部分。
第六步，看和节点5相邻的所有边。1-5、5-7不是横切边，所以不用再看；4-5:0.35其值小于最小索引堆索引为4处的值0.37，将其更新为0.35，同时将0.37这条边剔除.
然后从最小索引堆中找出最小边，即0.35这条边，它就是最小生成树的边。同时将结点4加入红色部分。
第七步，看和节点4相邻的所有横切边。此时只有4-6:0.93这一条横切边，其值大于此时最小索引堆中索引为6处的值0.40，所以将其剔除。
最后将最小索引堆中的0.40这条边取出，作为最小生成树的边。同时结点6加入红色部分。这时所有节点遍历完毕，并且找到了最小生成树。
这种方法对于不是横切边的边在判断后会扔掉，所以Prim的时间复杂度改进还是很可观的。
Prim算法代码
见附录2
Kruskal算法
Kruskal算法的主要思想是按照边的权重顺序(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入的边构成环，知道树中含有V-1条边为止。这些边逐渐由一片森林合并为一棵树，也就是图的最小生成树。——算法第四版
使用Kruskal算法，为了方便地每次都能取出最短的边，首先对图中所有的边按照权值排序。
然后就要取出还没有考虑的边中最短的那条边，看将此边加入到图中是否会生成环（如果生成环那么就不是最小生成树或者说不是树），如果没有生成环那么它就是最小生成树中的边。
第一步：0-7:0.16,将其放入最小生成树中，不会生成环，所以将这条边作为最小生成树中的一条边
第二步：下一条最小的边为2-3:0.17，将其放入最小生成树中，也不会生成环，所以它是最小生成树的一条边。
第三步：下一条最小的边为1-7:0.19，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
第四步：下一条最小的边为0-2:0.26，这里需要注意，虽然节点0和节点2都是红色，但是将这条边加入最小生成树后并没有形成环，所以它可以作为最小生成树的一条边。
第五步：下一条最小的边为5-7:0.28，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
第六步：下一条最小的边为1-3:0.29，将其放入最小生成树中，会生成环，不能作为最小生成树的一条边，所以不再考虑它。
第七步：下一条最小的边为1-5:0.32，将其放入最小生成树中，会生成环，所以不再考虑它。
第八步：下一条最小的边为2-7:0.34，将其放入最小生成树中，会生成环，所以不再考虑它。
第九步：下一条最小的边为4-5:0.35，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
第十步：下一条最小的边为1-2:0.36，将其放入最小生成树中，会生成环，所以不再考虑它。
第十一步、第十二步的边4-7:0.37、0-4:0.38，将其放入最小生成树中，会生成环，所以不再考虑它们。
第十三步：下一条最小的边为2-6:0.40，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
至此已经有了V-1条边，并且将V个顶点都连接起来了，这时候算法就可以结束了。如果继续扫描的话，剩下的边也都会让最小生成树形成环，也都不会被考虑，直到扫描结束。
整个过程中，关键的操作是判断加入一条边后，是否会行程一个环，这个操作可以使用并查集结构进行辅助。
那么如何使用并查集进行辅助呢？ 在每一次加入一条边作为最小生成树的同时，对一条边的两个端点进行Union操作。比如此时要加入1-3这条边，去找并查集中1的根节点和3的根节点，它们一定属于同一个根，说明最小生成树中已经连接了节点1和节点3了，此时再将1-3连接的话，就必然形成一个环，这时就可以不考虑这条边了。
Kruskal算法代码实现
见附录3
Kruskal算法的计算一副含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间和E成正比，所需的时间和ElogE成正比(最坏情况)。
与Prim算法一样，这个估计是比较保守的，因为算法在找到V-1条边之后就会终止。实际的成本应该与E+E0logE成正比，其中E0是权重小于最小生成树中权重最大的边的所有边的总数。尽管拥有这个优势，Kruskal算法一般还是比Prim算法要慢，因为在处理每条边时除了两种算法都要完成的优先队列操作之外，他还要进行一次connect()操作。
总结
Lazy Prim : O(ElogE) Prim : O(ElogV) 整体而言效率最高 Kruskal : O(ElogE)
在算法第四版有约定，所有边的权重都各不相同。但是如果有横切边相等的边，那么根据算法的具体实现，每次选择一个边，此时存在多个最小生成树。
另外还有个Vyssotsky's Algorithm提出的算法，将边逐渐的添加到生成树中，一旦形成环，就删除环中权值最大的边。这个过程完成后可以形成一个最小生成树。
附录1
首先创建最小堆MinHeap.java:
import java.util.*;
import java.lang.*;
// 在堆的有关操作中，需要比较堆中元素的大小，所以Item需要extends Comparable
public class MinHeap<Item extends Comparable> {
protected Item[] data;
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public MinHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
count = 0;
this.capacity = capacity;
}
// 构造函数, 通过一个给定数组创建一个最小堆
// 该构造堆的过程, 时间复杂度为O(n)
public MinHeap(Item arr[]){
int n = arr.length;
data = (Item[])new Comparable[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )
data[i+1] = arr[i];
count = n;
for( int i = count/2 ; i >= 1 ; i -- )
shiftDown(i);
}
// 返回堆中的元素个数
public int size(){
return count;
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty(){
return count == 0;
}
// 向最小堆中插入一个新的元素 item
public void insert(Item item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// 从最小堆中取出堆顶元素, 即堆中所存储的最小数据
public Item extractMin(){
assert count > 0;
Item ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// 获取最小堆中的堆顶元素
public Item getMin(){
assert( count > 0 );
return data[1];
}
// 交换堆中索引为i和j的两个元素
private void swap(int i, int j){
Item t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* 最小堆核心辅助函数
//********************
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) > 0 ){
swap(k, k/2);
k /= 2;
}
}
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置
if( j+1 <= count && data[j+1].compareTo(data[j]) < 0 )
j ++;
// data[j] 是 data[2*k]和data[2*k+1]中的最小值
if( data[k].compareTo(data[j]) <= 0 ) break;
swap(k, j);
k = j;
}
}
// 测试 MinHeap
public static void main(String[] args) {
MinHeap<Integer> minHeap = new MinHeap<Integer>(100);
int N = 100; // 堆中元素个数
int M = 100; // 堆中元素取值范围[0, M)
for( int i = 0 ; i < N ; i ++ )
minHeap.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// 将minheap中的数据逐渐使用extractMin取出来
// 取出来的顺序应该是按照从小到大的顺序取出来的
for( int i = 0 ; i < N ; i ++ ){
arr[i] = minHeap.extractMin();
System.out.print(arr[i] + " ");
}
System.out.println();
// 确保arr数组是从小到大排列的
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] <= arr[i];
}
}
然后创建LazyPrimMST.java类进行算法的编写.
import java.util.Vector;
public class LazyPrimMST<Weight extends Number & Comparable> {
private WeightedGraph<Weight> G; //图的引用
private MinHeap<Edge<Weight>> pq; //最小堆，算法辅助数据结构
private boolean[] marked; //标记数组，在算法运行过程中标记节点i是否被访问（即图中的蓝色部分和红色部分）
private Vector<Edge<Weight>> mst; //最小生成树所包含的所有边
private Number mstWeight; //最小生成树的权值
//构造函数，使用Prim算法求图的最小生成树
public LazyPrimMST(WeightedGraph<Weight> graph){
//算法初始化
G = graph;
pq = new MinHeap<Edge<Weight>>(G.E());
marked = new boolean[G.V()];
mst = new Vector<Edge<Weight>>();
//Lazy Prim
visit(0);
while (!pq.isEmpty()){
// 使用最小堆找出已经访问的边中权值最小的边
Edge<Weight> e = pq.extractMin();
// 如果这条边的两端都已经访问过了, 它不是横切边,扔掉这条边
if(marked[e.v()] == marked[e.w()])
continue;
//否则，这条边应该存在最小生成树中
mst.add(e);
//访问和这条边连接的还没有被访问过的节点(找到蓝色一端的端点)
if( !marked[e.v()] )
visit(e.v());
else
visit(e.w());
}
//计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for( int i = 1 ; i < mst.size() ; i ++)
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
//访问节点
private void visit(int v) {
if( marked[v] ){
throw new IllegalArgumentException("this point has been visited!");
}
marked[v] = true;
//将和节点v相连的所有未访问的边放入最小堆中
for(Edge<Weight> e : G.adj(v)){
if(!marked[e.other(v)]) //找到与其对应的另一个端点，如果是横切边
pq.insert(e); //就加入到堆中
}
}
// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
};
// 返回最小生成树的权值
Number result(){
return mstWeight;
};
}
在Main.java中进行测试:
import java.util.Vector;
public class Main {
// 测试通过文件读取图的信息
public static void main(String[] args) {
// 使用两种图的存储方式读取testG1.txt文件
String filename = "testG1.txt";
SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(8, false);
ReadWeightedGraph readGraph1 = new ReadWeightedGraph(g, filename);
// Test Lazy Prim MST
System.out.println("Test Lazy Prim MST:");
LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST<Double>(g);
Vector<Edge<Double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + lazyPrimMST.result());
System.out.println();
}
}
附录2
最小索引堆IndexMinHeap.java:
import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
// 最小索引堆
public class IndexMinHeap<Item extends Comparable> {
protected Item[] data; // 最小索引堆中的数据
protected int[] indexes; // 最小索引堆中的索引, indexes[x] = i 表示索引i在x的位置
protected int[] reverse; // 最小索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public IndexMinHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
indexes = new int[capacity+1];
reverse = new int[capacity+1];
for( int i = 0 ; i <= capacity ; i ++ )
reverse[i] = 0;
count = 0;
this.capacity = capacity;
}
// 返回索引堆中的元素个数
public int size(){
return count;
}
// 返回一个布尔值, 表示索引堆中是否为空
public boolean isEmpty(){
return count == 0;
}
// 向最小索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert(int i, Item item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
// 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
assert !contain(i);
i += 1;
data[i] = item;
indexes[count+1] = i;
reverse[i] = count + 1;
count ++;
shiftUp(count);
}
// 从最小索引堆中取出堆顶元素, 即索引堆中所存储的最小数据
public Item extractMin(){
assert count > 0;
Item ret = data[indexes[1]];
swapIndexes( 1 , count );
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return ret;
}
// 从最小索引堆中取出堆顶元素的索引
public int extractMinIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return ret;
}
// 获取最小索引堆中的堆顶元素
public Item getMin(){
assert count > 0;
return data[indexes[1]];
}
// 获取最小索引堆中的堆顶元素的索引
public int getMinIndex(){
assert count > 0;
return indexes[1]-1;
}
// 看索引i所在的位置是否存在元素
boolean contain( int i ){
assert i + 1 >= 1 && i + 1 <= capacity;
return reverse[i+1] != 0;
}
// 获取最小索引堆中索引为i的元素
public Item getItem( int i ){
assert contain(i);
return data[i+1];
}
// 将最小索引堆中索引为i的元素修改为newItem
public void change( int i , Item newItem ){
assert contain(i);
i += 1;
data[i] = newItem;
// 有了 reverse 之后,
// 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置
shiftUp( reverse[i] );
shiftDown( reverse[i] );
}
// 交换索引堆中的索引i和j
// 由于有了反向索引reverse数组，
// indexes数组发生改变以后， 相应的就需要维护reverse数组
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
reverse[indexes[i]] = i;
reverse[indexes[j]] = j;
}
//********************
//* 最小索引堆核心辅助函数
//********************
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) > 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k;
if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) < 0 )
j ++;
if( data[indexes[k]].compareTo(data[indexes[j]]) <= 0 )
break;
swapIndexes(k, j);
k = j;
}
}
// 测试 IndexMinHeap
public static void main(String[] args) {
int N = 1000000;
IndexMinHeap<Integer> indexMinHeap = new IndexMinHeap<Integer>(N);
for( int i = 0 ; i < N ; i ++ )
indexMinHeap.insert( i , (int)(Math.random()*N) );
}
}
PrimMST.java：
import java.util.Vector;
public class PrimMST<Weight extends Number & Comparable> {
private WeightedGraph G; //图的引用
private IndexMinHeap<Weight> ipq; //最小索引堆
private Edge<Weight>[] edgeTo; //访问的点所对应的边
private boolean[] marked; //标记数组,在算法运行过程中标记节点i是否被访问
private Vector<Edge<Weight>> mst; //最小生成树所包含的所有边
private Number mstWeight; //最小生成树的权值
//构造函数，使用Prim算法求图的最小生成树
public PrimMST(WeightedGraph graph){
G = graph;
if(!(graph.E() >= 1)){
throw new IllegalArgumentException("Edges of graph should >= 1");
}
ipq = new IndexMinHeap<>(graph.V()); //开辟顶点个数的空间就可以
//算法初始化
marked = new boolean[G.V()];
edgeTo = new Edge[G.V()];
for(int i = 0 ; i < G.V() ; i ++){
marked[i] = false;
edgeTo[i] = null;
}
mst = new Vector<Edge<Weight>>();
//Prim
visit(0);
while (!ipq.isEmpty()){
// 使用最小索引堆找出已经访问的边中权值最小的边
// 最小索引堆中存储的是点的索引, 通过点的索引找到相对应的边
int v = ipq.extractMinIndex();
if(edgeTo[v] == null){
throw new IllegalArgumentException("Edge should't be null");
}
mst.add(edgeTo[v]);
visit(v);
}
//计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for(int i = 1 ; i < mst.size() ; i ++){
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
//访问节点v
void visit(int v){
if( marked[v] ){
throw new IllegalArgumentException("this point has been visited!");
}
marked[v] = true;
// 将和节点v相连接的未访问的另一端点, 和与之相连接的边, 放入最小堆中
for(Object item :G.adj(v)){
Edge<Weight> e = (Edge<Weight>) item;
int w = e.other(v);
//如果边的另一端点未被访问
if(!marked[w]){
//如果从没有考虑过这个端点，直接将这个端点和与之相连接的边加入索引堆，即它是横切边
if(edgeTo[w] == null){
edgeTo[w] = e;
ipq.insert(w,e.wt());
}
//如果曾经考虑这个端点,但现在的边比之前考虑的边更短,则进行替换
else if(e.wt().compareTo(edgeTo[w].wt())< 0 ){
edgeTo[w] = e;
ipq.change(w,e.wt());
}
}
}
}
// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
Number result(){
return mstWeight;
}
// 测试 Prim
public static void main(String[] args) {
String filename = "testG1.txt";
int V = 8;
SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
// Test Prim MST
System.out.println("Test Prim MST:");
PrimMST<Double> primMST = new PrimMST<Double>(g);
Vector<Edge<Double>> mst = primMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + primMST.result());
System.out.println();
}
}
附录3
UnionFind.java:
// Union-Find
public class UnionFind {
// rank[i]表示以i为根的集合所表示的树的层数
// 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
// 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
private int[] rank;
private int[] parent; // parent[i]表示第i个元素所指向的父节点
private int count; // 数据个数
// 构造函数
public UnionFind(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此时, 我维护rank的值
}
}
}
MinHeap.java: 见附录1
KruskalMST.java:
import java.awt.event.WindowEvent;
import java.util.Vector;
public class KruskalMST<Weight extends Number & Comparable> {
private Vector<Edge<Weight>> mst; //最小生成树所包含的所有边
private Number mstWeight; //最小生成树的权值
//构造函数，使用Kruskal算法计算graph的最小生成树
public KruskalMST(WeightedGraph graph){
mst = new Vector<Edge<Weight>>();
//将所有的边进行排序，使用堆排序，将所有的边放入一个最小堆中
MinHeap<Edge<Weight>> pq = new MinHeap<Edge<Weight>>(graph.E());
for(int i = 0 ; i < graph.V(); i ++){
for(Object item : graph.adj(i)){
Edge<Weight> e = (Edge<Weight>) item;
if( e.v() <= e.w() ) //防止存入两次同一条边(比如边1-2和边2-1，只存入边1-2)
pq.insert(e);
}
}
// 创建一个并查集，查看已经访问的节点的联通情况
UnionFind uf = new UnionFind(graph.V());
while (!pq.isEmpty() && mst.size() < graph.V() - 1){//pq不为空且最小生成树的边数小于V-1
//从最小堆中依次从小到大取出所有的边
Edge<Weight> e = pq.extractMin();
//如果该边的两个端点是联通的，说明加入这条边将产生环，扔掉这条边
if(uf.isConnected(e.v(),e.w()))
continue;
//否则，将这条边加入最小生成树，同时标记边的两个端点联通
mst.add(e);
uf.unionElements(e.v(),e.w());
}
//计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for(int i = 1 ; i < mst.size() ; i ++){
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
Number result(){
return mstWeight;
}
// 测试 Kruskal
public static void main(String[] args) {
String filename = "testG1.txt";
int V = 8;
SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
// Test Kruskal
System.out.println("Test Kruskal:");
KruskalMST<Double> kruskalMST = new KruskalMST<Double>(g);
Vector<Edge<Double>> mst = kruskalMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + kruskalMST.result());
System.out.println();
}
}
测试结果: 
有权图
有权图是指在无权图的基础上，每一条边都有一个数值，代表两个结点之间有一定的数值关系，比如图用来表示路网时，权值可以表示两点之间的距离，到达彼此所需要的时间等。
有权图的邻接矩阵表达见下图:
有权图的邻接表表达见下图: s
邻接表每个节点后面存储两个信息:to表示和它相邻的节点的索引，w表示对应的边的权值.所以可以将这两个信息封装为Edge属性，它包含to和w属性。
当然要注意一点，邻接矩阵中依然用了传统的二维数组来存储，为了统一图的接口，也可以将a[i][j]位置存储为Edge格式。
这里就直接先写java代码了
创建WeightedGraph.java接口:
public interface WeightedGraph<Weight extends Number & Comparable> {
public int V(); //获取图的顶点数
public int E(); //获取图的边数
public void addEdge(Edge<Weight> e); //在v和w两个顶点间添加一条边
boolean hasEdge( int v , int w);//查看v和w两个顶点间是否有边
void show();//打印图
public Iterable<Edge<Weight>> adj(int v); //获取与v顶点连接的所有边
}
为了实现有权图，先编写一个Edge.java类:
//边
public class Edge<Weight extends Number & Comparable> implements Comparable<Edge> {
private int a,b; //边的两个端点
private Weight weight; //边的权值
public Edge(int a, int b , Weight weight){
this.a = a ;
this.b = b ;
this.weight = weight;
}
public Edge(Edge<Weight> e){
this.a = e.a;
this.b = e.b;
this.weight = e.weight;
}
public int v() {return a;} //返回第一个顶点
public int w() {return b;} //返回第二个顶点
public Weight wt() {return weight;} // 返回权值
//给定一个顶点，返回另一个顶点
public int other(int x){
if( x == a || x == b){
return x == a ? b : a;
}else
throw new IllegalArgumentException("x is not correct");
}
//输出边的信息
public String toString(){
return "" + a + "-" + b + ": " + weight;
}
@Override
public int compareTo(Edge that) {
if(weight.compareTo(that.wt()) < 0)
return -1;
else if(weight.compareTo(that.wt()) > 0)
return +1;
else
return 0;
}
}
在DenseGraph.java的基础上修改，创建DenseGraph.java:
import java.util.Vector;
public class DenseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph {
private int n; //节点数
private int m; //边数
private boolean directed; // 是否为有向图
private Edge<Weight>[][] g; //图的具体数据，用二维数组表达
//构造函数
public DenseWeightedGraph( int n , boolean directed){
if(n < 0)
throw new IllegalArgumentException("the value of n should be >= 0.");
this.n = n;
this.m = 0 ;//初始化时没有任何边
this.directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为null, 表示没有任和边
// false为boolean型变量的默认值
g = new Edge[n][n];
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ;j ++)
g[i][j] = null;
}
//返回节点个数
@Override
public int V() {
return n;
}
//返回边数
@Override
public int E() {
return m;
}
//向图中添加一条边
@Override
public void addEdge(Edge e) {
if(!(e.v() >= 0 && e.v() < n))
throw new IllegalArgumentException("you should type v >= 0 && v < n");
if(!(e.w() >= 0 && e.w() < n))
throw new IllegalArgumentException("you should type w >= 0 && w < n");
if(hasEdge(e.v(),e.w()))
return;
g[e.v()][e.w()] = new Edge(e);
if(e.v() != e.w() && !directed)
g[e.w()][e.v()] = new Edge(e.w(),e.v(),e.wt());
m ++;
}
//判断图中是否有v到w的边
@Override
public boolean hasEdge(int v, int w) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(w >= 0 && w < n))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
return g[v][w] != null;
}
//打印显示图的信息
@Override
public void show() {
for(int i = 0 ; i < n ; i ++){
for( int j = 0 ; j < n ; j ++)
if( g[i][j] != null)
System.out.println(g[i][j].wt()+"\t");
else
System.out.println("NULL\t");
System.out.println();
}
}
//返回图中v顶点的所有邻边
//由于java使用引用机制，返回一个Vector不会带来额外开销
@Override
public Iterable<Edge<Weight>> adj(int v) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
Vector<Edge<Weight>> adjV = new Vector<Edge<Weight>>();
for(int i = 0 ; i < n ; i++)
if(g[v][i] != null)
adjV.add(g[v][i]);
return adjV;
}
}
同样的修改SparseGraph.java后得到SparseWeightedGraph.java：
import java.util.Vector;
public class SparseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph {
private int n; //节点数
private int m; //边数
private boolean directed; //是否为有向图
private Vector<Edge<Weight>>[] g; //图的具体数据
//构造函数
public SparseWeightedGraph(int n , boolean directed){
if(n < 0)
throw new IllegalArgumentException("the value of n should be >= 0.");
this.n = n;
this.m = 0;
this.directed = directed;
//g初始化为n个空的vector,表示每一个g[i]都为空，即没有任何边
g = (Vector<Edge<Weight>>[]) new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Edge<Weight>>();
}
//返回节点个数
@Override
public int V() {
return n;
}
//返回边数
@Override
public int E() {
return m;
}
//向图中添加一条边
@Override
public void addEdge(Edge e) {
if(!(e.v() >= 0 && e.v() < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(e.w() >= 0 && e.w() < n))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
g[e.v()].add(new Edge<>(e));
if(e.v() != e.w() && !directed) //如果不是自环边，并且它是无向图，则创建w到v的边
g[e.w()].add(new Edge(e.w(),e.v(),e.wt()));
m ++;
}
//验证图中是否有v到w的边
@Override
public boolean hasEdge(int v, int w) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(w >= 0 && w < n))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
for(int i = 0 ; i < g[v].size() ; i++)
if( g[v].elementAt(i).other(v) == w)
return true;
return false;
}
//显示图的信息
@Override
public void show() {
for(int i = 0; i < n ; i ++){
System.out.printf("vertex %d :\t",i);
for(int j = 0 ; j < g[i].size() ; j++){
Edge e = g[i].elementAt(j);
System.out.print("( to:" + e.other(i) + ",wt:" + e.wt() + ")\t");
}
System.out.println();
}
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销,
@Override
public Iterable<Edge<Weight>> adj(int v) {
if(!(v >= 0 && v < n))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
return g[v];
}
}
修改ReadGraph.java后得到ReadWeightedGraph:
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class ReadWeightedGraph {
private Scanner scanner;
public ReadWeightedGraph(WeightedGraph<Double> graph , String filename){
readFile(filename);
try{
int V = scanner.nextInt();
if(V < 0 )
throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative");
assert V == graph.V();
int E = scanner.nextInt();
if(E < 0 )
throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");
for(int i = 0 ; i < E ; i ++){
int v = scanner.nextInt();
int w = scanner.nextInt();
Double weight = scanner.nextDouble(); //读取权值
if(!(v >= 0 && v < V))
throw new IllegalArgumentException("the value of v is Illegal!you should type the value of v between 0 and n.(v >=0 && v < n).");
if(!(w >= 0 && w < V))
throw new IllegalArgumentException("the value of w is Illegal!you should type the value of w between 0 and n.(w >=0 && w < n).");
graph.addEdge(new Edge<Double>(v,w,weight) );
}
}catch (InputMismatchException e){
String token = scanner.next();
throw new InputMismatchException("attempts to read an 'int' value from input stream,but the next token is \""+token +"\"");
}catch(NoSuchElementException e){
throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available");
}
}
private void readFile(String filename){
if(filename == null)
throw new IllegalArgumentException("filename should not be null!");
try {
File file = new File(filename);
if (file.exists()) {
FileInputStream fis = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
scanner.useLocale(Locale.ENGLISH);
}else
throw new IllegalArgumentException(filename + "doesn't exists.");
}catch (IOException ex){
throw new IllegalArgumentException("Could not open " + filename,ex);
}
}
}
测试文件testG1.txt:
8 16
4 5 .35
4 7 .37
5 7 .28
0 7 .16
1 5 .32
0 4 .38
2 3 .17
1 7 .19
0 2 .26
1 2 .36
1 3 .29
2 7 .34
6 2 .40
3 6 .52
6 0 .58
6 4 .93
在Main.java中进行测试:
public class Main {
// 测试通过文件读取图的信息
public static void main(String[] args) {
// 使用两种图的存储方式读取testG1.txt文件
String filename = "testG1.txt";
SparseWeightedGraph<Double> g1 = new SparseWeightedGraph<Double>(8, false);
ReadWeightedGraph readGraph1 = new ReadWeightedGraph(g1, filename);
System.out.println("test G1 in Sparse Weighted Graph:");
g1.show();
System.out.println();
DenseWeightedGraph<Double> g2 = new DenseWeightedGraph<Double>(8, false);
ReadWeightedGraph readGraph2 = new ReadWeightedGraph(g2 , filename );
System.out.println("test G1 in Dense Graph:");
g2.show();
System.out.println();
}
}
最小生成树问题
算法（第四版）中的定义： 最小生成树。给定一个加权无向图，找到它的一棵最小生成树（Minimum Span Tree）。
如果一个图有v个节点，那么就应该有v-1条边连接这V个节点，这就是这个图的生成树。不仅如此，这v-1条边连接了所有的v个节点，这v-1条边的权值相加也是最小的，如何找到这个生成树，就是最小生成树问题。
一些约定
这里在计算最小生成树的过程中会出现各种特殊情况，所以为了行文流畅，进行约定：
- 只考虑连通图
- 针对带权无向图
- 所有边的权重都各不相同
所以在进行最小生成树相关算法的过程中要找V-1条边，连接V个顶点使得其总权值最小。
切分定理 - Cut Property
把图中的结点分为两个部分，成为一个切分(Cut).
如下图就是一个切分:
如果一个边的两个端点，属于切分(Cut)不同的两边，这个边称为横切边(Crossing Edge).
如下图的蓝色线条就是横切边:
切分定理的定义： 在一副加权图中，给定任意切分，横切边中权值最小的边必然属于图的最小生成树。
例如上图中的权重为0.4的边肯定是最小生成树的一条边:
算法(第四版)中的证明:
今e为权重最小的横切边，T为图的最小生成树。我们采用反证法:假设T不包含e。那么如果将e加入T，得到的图必然含有一条经过e的环，且这个环至少含有另一条横切边——设为f，f的权重必然大于e(因为e的权重是最小的且图中所有边的权重均不同)。那么我们删掉f而保留e就可以得到一棵权重更小的生成树。这和我们的假设T矛盾。
在假设所有的边的权重均不相同的前提下，每幅连通图都只有一棵唯一的最小生成树，切分定理也表明了对于每一种切分，权重最小的横切边必然属于最小生成树。
切分定理是解决最小生成树问题的所有算法的基础。更确切的说，这些算法都是一种贪心算法的特殊情况:使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。这些算法相互之间的不同之处在于保存切分和判定权重最小的横切边的方式。
Lazy Prim算法
首先将一个起始节点作为切分的一部分，这里从0节点开始。将0节点作为切分的一部分，剩下的节点作为切分的另一部分。每一次找到横切边中权值最小的边。这里可以使用最小堆，将横切边放入最小堆中，作为最小生成树所包含的边的候选。这些边进入堆后，下一步只需拿出最小堆中的最短边就可以了。
这一步找出的是0-7:0.16权值为0.16的边，它一定属于最小生成树。
第二步，确定了0-7这条边为最小生成树的一条边，而结点7没有被访问过，此时就可以将结点7加入到红色节点部分，这样就形成了一个新的切分。这个新的切分就和另一部分切分形成了新的横切边。
然后将这些新的横切边推入最小堆，然后在最小堆中选出权值最小的边1-7:0.19。
第三步，确定了1-7为最小生成树的一条边，而节点1没有被访问过，此时将结点1加入到红色结点部分，这样又形成了一个新的切分。也相应的和另一部分切分形成了新的横切边。将这些新的横切边加入到最小堆。
接着看在候选的横切边中，最短的边为0-2:0.26的边。
第四步，确定了0-2为最小生成树的一条边，而结点2没有被访问过，所以将结点2加入红色结点部分，这样就又形成一个新的切分。又有新的边成为了横切边。将他们加入到最小堆中。
此时需要注意，将结点2加入到红色部分后，最小堆中蓝色的部分中，边2-7:0.34和边1-2:0.36，实际上已经不是横切边了，所以这两条边不应该成为最小生成树的边的候选了。所以这里体现出Lazy Prim算法的”懒惰”性，当前这两条边虽然不可能成为最小生成树的候选边，但是这里不需要着急将其剔除，先将其保留在最小堆中，当拿出这两条边时，发现这两条边不是横切边时，再将这两条边剔除。
接着在最小堆中寻找最小的边，最短边为2-3:0.17的边.
第五步，确定了2-3为最小生成树的一条边，而结点3没有被访问过，所以将结点3加入到红色结点部分，形成新的切分后，将新的横切边加入到最小堆中。
接着最小堆中的最小边应该是5-7:0.28的边。
第六步，确定了5-7为最小生成树的一条边，而结点5没有被访问过，所以将结点5加入到红色部分，形成新的切分并将新的横切边加入到最小堆中。
接着看在最小堆中，最小的边为1-3:0.29的边，当将其拿出后发现，结点1和结点3都是红色的结点，即这条边不是一条横切边（只有横切边中的最小边才是最小生成树的边），所以将其拿出后剔除。接着看在最小堆中的最短边为1-5:0.32的边，拿出后发现结点1和结点5都是红色的结点，所以也要将其剔除。接着看剩下的最小堆中的最短边为2-7:0.34，也不满足横切边的性质，剔除。 接着看剩下的最小堆中的最短边为4-5:0.35，满足横切边的性质，所以将这条边作为最小生成树的边。
第七步，确定了5-4为最小生成树的一条边，由于结点4没有被访问过，所以将结点4加入到红色部分，行成新的切分并将新的横切边4-6:0.93加入到最小堆中。
然后在最小堆中找最短的边，为1-2:0.36这条边，但是它不是横切边，将其剔除。接着最小堆中最短的边为4-7:0.37，它不是横切边，将其剔除。继续找最小堆中最短边为0-4:0.38，不是横切边，将其剔除。 继续找最小堆中的最短边为2-6:0.40，它是横切边，将其作为最小生成树的边。
由于结点6没有被访问过，将其加入到红色部分。这时所有节点都在红色部分，程序至此就可以结束。
如果以最小堆中的边为空作为判断依据的话，那么依然可以拿出最小堆中的最小边进行判断，此时所有的边都不是横切边，将剩下的边判断完后，程序结束。
此时就用Lazy Prim算法获得了最小生成树。
Lazy Prim算法代码
见附录1
Prim算法的优化
pq.extractMin()操作的时间复杂度为O(logE),因为pq中最多承载E条边。 visit()操作时，遍历节点的所有临边，合在一起也是O(E)，如果是邻接矩阵就是O(V^2)，在稠密图的邻接矩阵中O(V^2)和O(E)是一个级别的。同时其中有个add()操作，它是O(logE)级别的。
所以，Lazy Prim算法的时间复杂度为O(ElogE).
通过优化，Prim算法的时间复杂度可以改进为O(ElogV).
Lazy Prim算法的一个问题就是，所有的边都要进入最小堆，随着切分的进行，很多已经不是横切边的边仍在最小堆中。另一问题是，虽然有很多横切边，但我们只关注最短的那个横切边，尤其是和一个节点相连的很多横切边，其实只需考虑和这个点相连的最短的横切边就可以了。
基于这个思想，需要维护一个数据结构——存储和每个节点相连的那个最短的横切边。在不断增加红色节点改变切分的过程中，只要不断更新和每个节点相连的最短的横切边就可以了。即这个数据结构要满足：①它能取到最小值②能够供我们更新。所以需要使用IndexMinHeap.
第一步: 以0作为起点开始，由于最小生成树有V-1个边，而IndexMinHeap有V个空间，所以肯定有一个节点不需要存储任何东西。就将初始结点作为不需要存储东西的节点。此时有了初始节点后，相当于有了切分，这时，这个节点的所有临边都是横切边，这种情况下，就将这些横切边加入到IndexMinHeap中。 此时，和2相连的横切边，最小权值是0.26;和4相连的横切边，最小权值是0.38;和6相连的横切边，最小权值是0.58;和7相连的横切边，最小权值是0.16.
这时，从IndexMinHeap中找出权值最小的一条边，根据切分定理，一定是最小生成树的边，即0.16这条边。这时节点7加入红色部分。
第二步，由于结点7加入了红色部分。要考虑更多的横切边，这时遍历结点7的临边。先看1-7，此时IndexMinHeap中没有和1相连的横切边权值最小的边，所以IndexMinHeap中1的值更新为0.19;再看2-7，其值为0.34，而IndexMinHeap中和2相连的横切边权值最小的是0-2:0.26，所以2-7肯定不会是最小生成树中的一条边，可以直接剔除；接着看4-7，这个边的权值为0.37,它小于当前IndexMinHeap中存储的0.38，所以将4-7:0.37更新到最小索引堆中，与此同时，意味着将0-4:0.38这条边丢弃，因为这条边不可能会是最小生成树的边;最后，看5-7，这个边的权值为0.28，当前IndexMinHeap和5相连的边还没有，所以将其放入IndexMinHeap索引为5的位置中。这时候就完成了visit(7)操作。
然后从最小索引堆IndexMinHeap中找出权值最小的边，即和1相连的1-7:0.19这条边，可以确定它属于最小生成树。因此结点1也可以加入红色部分
第三步，看和结点1相邻的所有边。首先是1-2:0.36，在IndexMinHeap中索引为2的位置其值为0.26，所以1-2不是最小生成树的边；接着看1-5:0.32，但是在IndexMinHeap中和5相连的横切边最小的值为0.28，所以它也不是最小生成树的边;最后看1-3:0.29，由于IndexMinHeap中没有和3相连的横切边，将其放入IndexMinHeap中。
然后从最小索引堆中找出权值最小的边，即和2相连的0-2:0.26这条边，可以确定它属于最小生成树。与此同时结点2加入红色部分。
第四步，看和结点2相邻的所有边。这里注意2-7和1-2不是横切边，所以不用再看了；然后看2-3:0.17，此时最小索引堆中索引为3的位置的值为0.29，所以将其更新为0.17,同时0.29这条边可以剔除不在考虑;接着看2-6:0.40，此时最小索引堆中的索引为6的位置的值为0.58，所以将其更新为0.40，同时0.58这条边可以剔除不在考虑了.
然后从最小索引堆中取出权值最小的边，即和3相连的0.17这条边，根据切分定理，其一定属于最小生成树。同时，将接点3加入红色部分。
第五步，看和接点3相邻的所有边。1-3不是横切边，所以不用看；剩下一条3-6:0.52,其值0.52大于最小索引堆索引为6处的0.40，所以这条边剔除不再考虑。
然后从最小索引堆中找出权值最小的边，即和5相连的0.28这条边，它一定是最小生成树的边。同时将结点5加入红色部分。
第六步，看和节点5相邻的所有边。1-5、5-7不是横切边，所以不用再看；4-5:0.35其值小于最小索引堆索引为4处的值0.37，将其更新为0.35，同时将0.37这条边剔除.
然后从最小索引堆中找出最小边，即0.35这条边，它就是最小生成树的边。同时将结点4加入红色部分。
第七步，看和节点4相邻的所有横切边。此时只有4-6:0.93这一条横切边，其值大于此时最小索引堆中索引为6处的值0.40，所以将其剔除。
最后将最小索引堆中的0.40这条边取出，作为最小生成树的边。同时结点6加入红色部分。这时所有节点遍历完毕，并且找到了最小生成树。
这种方法对于不是横切边的边在判断后会扔掉，所以Prim的时间复杂度改进还是很可观的。
Prim算法代码
见附录2
Kruskal算法
Kruskal算法的主要思想是按照边的权重顺序(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入的边构成环，知道树中含有V-1条边为止。这些边逐渐由一片森林合并为一棵树，也就是图的最小生成树。——算法第四版
使用Kruskal算法，为了方便地每次都能取出最短的边，首先对图中所有的边按照权值排序。
然后就要取出还没有考虑的边中最短的那条边，看将此边加入到图中是否会生成环（如果生成环那么就不是最小生成树或者说不是树），如果没有生成环那么它就是最小生成树中的边。
第一步：0-7:0.16,将其放入最小生成树中，不会生成环，所以将这条边作为最小生成树中的一条边
第二步：下一条最小的边为2-3:0.17，将其放入最小生成树中，也不会生成环，所以它是最小生成树的一条边。
第三步：下一条最小的边为1-7:0.19，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
第四步：下一条最小的边为0-2:0.26，这里需要注意，虽然节点0和节点2都是红色，但是将这条边加入最小生成树后并没有形成环，所以它可以作为最小生成树的一条边。
第五步：下一条最小的边为5-7:0.28，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
第六步：下一条最小的边为1-3:0.29，将其放入最小生成树中，会生成环，不能作为最小生成树的一条边，所以不再考虑它。
第七步：下一条最小的边为1-5:0.32，将其放入最小生成树中，会生成环，所以不再考虑它。
第八步：下一条最小的边为2-7:0.34，将其放入最小生成树中，会生成环，所以不再考虑它。
第九步：下一条最小的边为4-5:0.35，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
第十步：下一条最小的边为1-2:0.36，将其放入最小生成树中，会生成环，所以不再考虑它。
第十一步、第十二步的边4-7:0.37、0-4:0.38，将其放入最小生成树中，会生成环，所以不再考虑它们。
第十三步：下一条最小的边为2-6:0.40，将其放入最小生成树中，不会生成环，所以它是最小生成树的一条边。
至此已经有了V-1条边，并且将V个顶点都连接起来了，这时候算法就可以结束了。如果继续扫描的话，剩下的边也都会让最小生成树形成环，也都不会被考虑，直到扫描结束。
整个过程中，关键的操作是判断加入一条边后，是否会行程一个环，这个操作可以使用并查集结构进行辅助。
那么如何使用并查集进行辅助呢？ 在每一次加入一条边作为最小生成树的同时，对一条边的两个端点进行Union操作。比如此时要加入1-3这条边，去找并查集中1的根节点和3的根节点，它们一定属于同一个根，说明最小生成树中已经连接了节点1和节点3了，此时再将1-3连接的话，就必然形成一个环，这时就可以不考虑这条边了。
Kruskal算法代码实现
见附录3
Kruskal算法的计算一副含有V个顶点和E条边的连通加权无向图的最小生成树所需的空间和E成正比，所需的时间和ElogE成正比(最坏情况)。
与Prim算法一样，这个估计是比较保守的，因为算法在找到V-1条边之后就会终止。实际的成本应该与E+E0logE成正比，其中E0是权重小于最小生成树中权重最大的边的所有边的总数。尽管拥有这个优势，Kruskal算法一般还是比Prim算法要慢，因为在处理每条边时除了两种算法都要完成的优先队列操作之外，他还要进行一次connect()操作。
总结
Lazy Prim : O(ElogE) Prim : O(ElogV) 整体而言效率最高 Kruskal : O(ElogE)
在算法第四版有约定，所有边的权重都各不相同。但是如果有横切边相等的边，那么根据算法的具体实现，每次选择一个边，此时存在多个最小生成树。
另外还有个Vyssotsky's Algorithm提出的算法，将边逐渐的添加到生成树中，一旦形成环，就删除环中权值最大的边。这个过程完成后可以形成一个最小生成树。
附录1
首先创建最小堆MinHeap.java:
import java.util.*;
import java.lang.*;
// 在堆的有关操作中，需要比较堆中元素的大小，所以Item需要extends Comparable
public class MinHeap<Item extends Comparable> {
protected Item[] data;
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public MinHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
count = 0;
this.capacity = capacity;
}
// 构造函数, 通过一个给定数组创建一个最小堆
// 该构造堆的过程, 时间复杂度为O(n)
public MinHeap(Item arr[]){
int n = arr.length;
data = (Item[])new Comparable[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )
data[i+1] = arr[i];
count = n;
for( int i = count/2 ; i >= 1 ; i -- )
shiftDown(i);
}
// 返回堆中的元素个数
public int size(){
return count;
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty(){
return count == 0;
}
// 向最小堆中插入一个新的元素 item
public void insert(Item item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// 从最小堆中取出堆顶元素, 即堆中所存储的最小数据
public Item extractMin(){
assert count > 0;
Item ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// 获取最小堆中的堆顶元素
public Item getMin(){
assert( count > 0 );
return data[1];
}
// 交换堆中索引为i和j的两个元素
private void swap(int i, int j){
Item t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* 最小堆核心辅助函数
//********************
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) > 0 ){
swap(k, k/2);
k /= 2;
}
}
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置
if( j+1 <= count && data[j+1].compareTo(data[j]) < 0 )
j ++;
// data[j] 是 data[2*k]和data[2*k+1]中的最小值
if( data[k].compareTo(data[j]) <= 0 ) break;
swap(k, j);
k = j;
}
}
// 测试 MinHeap
public static void main(String[] args) {
MinHeap<Integer> minHeap = new MinHeap<Integer>(100);
int N = 100; // 堆中元素个数
int M = 100; // 堆中元素取值范围[0, M)
for( int i = 0 ; i < N ; i ++ )
minHeap.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// 将minheap中的数据逐渐使用extractMin取出来
// 取出来的顺序应该是按照从小到大的顺序取出来的
for( int i = 0 ; i < N ; i ++ ){
arr[i] = minHeap.extractMin();
System.out.print(arr[i] + " ");
}
System.out.println();
// 确保arr数组是从小到大排列的
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] <= arr[i];
}
}
然后创建LazyPrimMST.java类进行算法的编写.
import java.util.Vector;
public class LazyPrimMST<Weight extends Number & Comparable> {
private WeightedGraph<Weight> G; //图的引用
private MinHeap<Edge<Weight>> pq; //最小堆，算法辅助数据结构
private boolean[] marked; //标记数组，在算法运行过程中标记节点i是否被访问（即图中的蓝色部分和红色部分）
private Vector<Edge<Weight>> mst; //最小生成树所包含的所有边
private Number mstWeight; //最小生成树的权值
//构造函数，使用Prim算法求图的最小生成树
public LazyPrimMST(WeightedGraph<Weight> graph){
//算法初始化
G = graph;
pq = new MinHeap<Edge<Weight>>(G.E());
marked = new boolean[G.V()];
mst = new Vector<Edge<Weight>>();
//Lazy Prim
visit(0);
while (!pq.isEmpty()){
// 使用最小堆找出已经访问的边中权值最小的边
Edge<Weight> e = pq.extractMin();
// 如果这条边的两端都已经访问过了, 它不是横切边,扔掉这条边
if(marked[e.v()] == marked[e.w()])
continue;
//否则，这条边应该存在最小生成树中
mst.add(e);
//访问和这条边连接的还没有被访问过的节点(找到蓝色一端的端点)
if( !marked[e.v()] )
visit(e.v());
else
visit(e.w());
}
//计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for( int i = 1 ; i < mst.size() ; i ++)
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
//访问节点
private void visit(int v) {
if( marked[v] ){
throw new IllegalArgumentException("this point has been visited!");
}
marked[v] = true;
//将和节点v相连的所有未访问的边放入最小堆中
for(Edge<Weight> e : G.adj(v)){
if(!marked[e.other(v)]) //找到与其对应的另一个端点，如果是横切边
pq.insert(e); //就加入到堆中
}
}
// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
};
// 返回最小生成树的权值
Number result(){
return mstWeight;
};
}
在Main.java中进行测试:
import java.util.Vector;
public class Main {
// 测试通过文件读取图的信息
public static void main(String[] args) {
// 使用两种图的存储方式读取testG1.txt文件
String filename = "testG1.txt";
SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(8, false);
ReadWeightedGraph readGraph1 = new ReadWeightedGraph(g, filename);
// Test Lazy Prim MST
System.out.println("Test Lazy Prim MST:");
LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST<Double>(g);
Vector<Edge<Double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + lazyPrimMST.result());
System.out.println();
}
}
附录2
最小索引堆IndexMinHeap.java:
import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
// 最小索引堆
public class IndexMinHeap<Item extends Comparable> {
protected Item[] data; // 最小索引堆中的数据
protected int[] indexes; // 最小索引堆中的索引, indexes[x] = i 表示索引i在x的位置
protected int[] reverse; // 最小索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public IndexMinHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
indexes = new int[capacity+1];
reverse = new int[capacity+1];
for( int i = 0 ; i <= capacity ; i ++ )
reverse[i] = 0;
count = 0;
this.capacity = capacity;
}
// 返回索引堆中的元素个数
public int size(){
return count;
}
// 返回一个布尔值, 表示索引堆中是否为空
public boolean isEmpty(){
return count == 0;
}
// 向最小索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert(int i, Item item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
// 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
assert !contain(i);
i += 1;
data[i] = item;
indexes[count+1] = i;
reverse[i] = count + 1;
count ++;
shiftUp(count);
}
// 从最小索引堆中取出堆顶元素, 即索引堆中所存储的最小数据
public Item extractMin(){
assert count > 0;
Item ret = data[indexes[1]];
swapIndexes( 1 , count );
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return ret;
}
// 从最小索引堆中取出堆顶元素的索引
public int extractMinIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return ret;
}
// 获取最小索引堆中的堆顶元素
public Item getMin(){
assert count > 0;
return data[indexes[1]];
}
// 获取最小索引堆中的堆顶元素的索引
public int getMinIndex(){
assert count > 0;
return indexes[1]-1;
}
// 看索引i所在的位置是否存在元素
boolean contain( int i ){
assert i + 1 >= 1 && i + 1 <= capacity;
return reverse[i+1] != 0;
}
// 获取最小索引堆中索引为i的元素
public Item getItem( int i ){
assert contain(i);
return data[i+1];
}
// 将最小索引堆中索引为i的元素修改为newItem
public void change( int i , Item newItem ){
assert contain(i);
i += 1;
data[i] = newItem;
// 有了 reverse 之后,
// 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置
shiftUp( reverse[i] );
shiftDown( reverse[i] );
}
// 交换索引堆中的索引i和j
// 由于有了反向索引reverse数组，
// indexes数组发生改变以后， 相应的就需要维护reverse数组
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
reverse[indexes[i]] = i;
reverse[indexes[j]] = j;
}
//********************
//* 最小索引堆核心辅助函数
//********************
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) > 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k;
if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) < 0 )
j ++;
if( data[indexes[k]].compareTo(data[indexes[j]]) <= 0 )
break;
swapIndexes(k, j);
k = j;
}
}
// 测试 IndexMinHeap
public static void main(String[] args) {
int N = 1000000;
IndexMinHeap<Integer> indexMinHeap = new IndexMinHeap<Integer>(N);
for( int i = 0 ; i < N ; i ++ )
indexMinHeap.insert( i , (int)(Math.random()*N) );
}
}
PrimMST.java：
import java.util.Vector;
public class PrimMST<Weight extends Number & Comparable> {
private WeightedGraph G; //图的引用
private IndexMinHeap<Weight> ipq; //最小索引堆
private Edge<Weight>[] edgeTo; //访问的点所对应的边
private boolean[] marked; //标记数组,在算法运行过程中标记节点i是否被访问
private Vector<Edge<Weight>> mst; //最小生成树所包含的所有边
private Number mstWeight; //最小生成树的权值
//构造函数，使用Prim算法求图的最小生成树
public PrimMST(WeightedGraph graph){
G = graph;
if(!(graph.E() >= 1)){
throw new IllegalArgumentException("Edges of graph should >= 1");
}
ipq = new IndexMinHeap<>(graph.V()); //开辟顶点个数的空间就可以
//算法初始化
marked = new boolean[G.V()];
edgeTo = new Edge[G.V()];
for(int i = 0 ; i < G.V() ; i ++){
marked[i] = false;
edgeTo[i] = null;
}
mst = new Vector<Edge<Weight>>();
//Prim
visit(0);
while (!ipq.isEmpty()){
// 使用最小索引堆找出已经访问的边中权值最小的边
// 最小索引堆中存储的是点的索引, 通过点的索引找到相对应的边
int v = ipq.extractMinIndex();
if(edgeTo[v] == null){
throw new IllegalArgumentException("Edge should't be null");
}
mst.add(edgeTo[v]);
visit(v);
}
//计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for(int i = 1 ; i < mst.size() ; i ++){
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
//访问节点v
void visit(int v){
if( marked[v] ){
throw new IllegalArgumentException("this point has been visited!");
}
marked[v] = true;
// 将和节点v相连接的未访问的另一端点, 和与之相连接的边, 放入最小堆中
for(Object item :G.adj(v)){
Edge<Weight> e = (Edge<Weight>) item;
int w = e.other(v);
//如果边的另一端点未被访问
if(!marked[w]){
//如果从没有考虑过这个端点，直接将这个端点和与之相连接的边加入索引堆，即它是横切边
if(edgeTo[w] == null){
edgeTo[w] = e;
ipq.insert(w,e.wt());
}
//如果曾经考虑这个端点,但现在的边比之前考虑的边更短,则进行替换
else if(e.wt().compareTo(edgeTo[w].wt())< 0 ){
edgeTo[w] = e;
ipq.change(w,e.wt());
}
}
}
}
// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
Number result(){
return mstWeight;
}
// 测试 Prim
public static void main(String[] args) {
String filename = "testG1.txt";
int V = 8;
SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
// Test Prim MST
System.out.println("Test Prim MST:");
PrimMST<Double> primMST = new PrimMST<Double>(g);
Vector<Edge<Double>> mst = primMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + primMST.result());
System.out.println();
}
}
附录3
UnionFind.java:
// Union-Find
public class UnionFind {
// rank[i]表示以i为根的集合所表示的树的层数
// 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
// 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
private int[] rank;
private int[] parent; // parent[i]表示第i个元素所指向的父节点
private int count; // 数据个数
// 构造函数
public UnionFind(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此时, 我维护rank的值
}
}
}
MinHeap.java: 见附录1
KruskalMST.java:
import java.awt.event.WindowEvent;
import java.util.Vector;
public class KruskalMST<Weight extends Number & Comparable> {
private Vector<Edge<Weight>> mst; //最小生成树所包含的所有边
private Number mstWeight; //最小生成树的权值
//构造函数，使用Kruskal算法计算graph的最小生成树
public KruskalMST(WeightedGraph graph){
mst = new Vector<Edge<Weight>>();
//将所有的边进行排序，使用堆排序，将所有的边放入一个最小堆中
MinHeap<Edge<Weight>> pq = new MinHeap<Edge<Weight>>(graph.E());
for(int i = 0 ; i < graph.V(); i ++){
for(Object item : graph.adj(i)){
Edge<Weight> e = (Edge<Weight>) item;
if( e.v() <= e.w() ) //防止存入两次同一条边(比如边1-2和边2-1，只存入边1-2)
pq.insert(e);
}
}
// 创建一个并查集，查看已经访问的节点的联通情况
UnionFind uf = new UnionFind(graph.V());
while (!pq.isEmpty() && mst.size() < graph.V() - 1){//pq不为空且最小生成树的边数小于V-1
//从最小堆中依次从小到大取出所有的边
Edge<Weight> e = pq.extractMin();
//如果该边的两个端点是联通的，说明加入这条边将产生环，扔掉这条边
if(uf.isConnected(e.v(),e.w()))
continue;
//否则，将这条边加入最小生成树，同时标记边的两个端点联通
mst.add(e);
uf.unionElements(e.v(),e.w());
}
//计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for(int i = 1 ; i < mst.size() ; i ++){
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
// 返回最小生成树的所有边
Vector<Edge<Weight>> mstEdges(){
return mst;
}
// 返回最小生成树的权值
Number result(){
return mstWeight;
}
// 测试 Kruskal
public static void main(String[] args) {
String filename = "testG1.txt";
int V = 8;
SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);
// Test Kruskal
System.out.println("Test Kruskal:");
KruskalMST<Double> kruskalMST = new KruskalMST<Double>(g);
Vector<Edge<Double>> mst = kruskalMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
System.out.println(mst.elementAt(i));
System.out.println("The MST weight is: " + kruskalMST.result());
System.out.println();
}
}
测试结果: