加权无向图的实现
加权无向图的实现最简单的方法是扩展无向图的表示方法：在邻接表的表示中，可以在链表的结点中增加一个权重域。但这里用另一个方法来实现：我们实现两个类，权重边类和无向图类。无向图类中组合权重边类来实现加权无向图。
权重边类：
public class Edge implements Comparable<Edge> { //实现Comparable接口private int v;private int w;private double weight;public Edge(int v,int w,double weight){ this.v = v; this.w = w; this.weight = weight;}//获取边的一个结点和另一个节点public int either() {return v;}public int other(int vertex) {if(vertex == v) return w;else if(vertex == w) return v;}//实现接口中的compareTo()方法public int compareTo(Edge that) {if(this.weight() < that.weight()) return -1;else if(this.weight() > that.weight()) return 1;else return 0;}public double weight() {return weight;}public String toString() { return String.format("%d-%d %.2f", v,w,weight); }
}加权无向图类：
public class EdgeWeightedGraph {private int V;//顶点数private int E;//边数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 int V() {return V;}public int E() {return E;}//添加边public void addEdge(Edge e) {//获取边的两个顶点int v = e.either();int w = e.other(v);//因为是无向图，互相添加边，调用的是背包的add()方法adj[v].add(e); adj[w].add(e);E++;}//和v相关联的所有边public Iterable<Edge> adj(int v){ return adj[v]; }//图的所有边public Iterable<Edge> edges(){Bag<Edge> b = new Bag<Edge>();for(int v = 0; v <V ; v++)for(Edge e : adj[v])if(e.other(v)>v) b.add(e);return b;}
}Prim算法：
图的生成树是它的一棵含有其所有顶点的无环连通子图，加权图的最小生成树（MST）是它的一棵权值最小的生成树。 Prim算法能够得到任意加权连通无向图的最小生成树。
切分：
图的一种切分是将图的所有顶点分为两个非空且不重合的两个集合。横切边是一条连接两个属于不同集合的顶点的边。
切分定理：在一幅加权图中，给定任意的切分，它横切边中权重最小者必然属于图的最小生成树。
切分定理是解决最小生成树问题的所有算法的基础。
数据结构：
- 采用一个布尔数组marked[]来记录顶点是否在树中，如果顶点v在，则marked[v]为true。
- 使用一条优先权队列来保存所有的横切边。
- 使用一条队列保存最小生成树的边。
算法思想：
使用一个最小优先权队列保存横切边集合，每次新加进来一个结点，就将和该结点关联的所有边添加进最小优先权队列；生成最小树时，从横切边集合中取出最小边，判断是否和目前的树产生环，如果产生环，则舍弃该边；否则将该边加入最小生成树队列。
Prim算法延时实现：
延时实现比较简单，它会在优先权队列中保存已经失效的边。
public class LazyPrimMST {private boolean[] marked;//最小生成树的顶点private Queue<Edge> mst;//最小生成树的边private MinPQ<Edge> pq;//横切边（包括已经失效的边）public LazyPrimMST(EdgeWeightedGraph G) {pq = new MinPQ<Edge>();marked = new boolean[G.V()];mst = new Queue<Edge>();visit(G,0);//从顶点0 开始while(!pq.isEmpty()) {//构造最小生成树Edge e = pq.delMin();int v = e.either(),w = e.other(v);if(marked[v]&&marked[w])continue;//跳过失效的边mst.enqueue(e);//将边添加到树中if(!marked[v]) visit(G,v);if(!marked[w]) visit(G,w);}}private void visit(EdgeWeightedGraph G,int v) {//更新横切边集合marked[v] = true;for(Edge e:G.adj(v))if(!marked[e.other(v)]) pq.insert(e);}public Iterable<Edge> edges(){//返回最小生成树return mst;}
}Prim算法的延时实现计算一个含V个顶点和E条边的连通加权无向图的最小生成树所需空间与E成正比，所需时间与ElogE成正比（最坏情况）。
Prim算法即时实现：
要改进LazyPrimMST,可以尝试从优先队列中删除用不到的边。关键在于，我们关注的只是连接树顶点和非树顶点中权重最小的边。当我们将顶点v加入树中，只可能使非树顶点w到最小生成树更近了。简而言之，我们不必保存所有从w到树顶点的边， 只需保存最小的那条即可。在v添加进树中时遍历v的邻接表检查是否需要更新权重最小的边。
引进两个顶点索引数组edgeTo[]和distTo[],它们有如下性质：
- 如果顶点v不在树中但至少含有一条边和树相连，那么edgeTo[v]将是v和树连接的最短的边，distTo[v]为这条边的权重。
- 所有这类v都保存在一条索引优先队列中，索引v关联的值是edgeTo[v]的边的权重。
public class PrimMST {private Edge[] edgeTo;//距离树最近的边private double[] distTo;//distTo[w] = edgeTo[w].weight()private boolean[] marked;//如果v在树中则为trueprivate IndexMinPQ<Double> pq;//有效横切边public PrimMST(EdgeWeightedGraph G) {edgeTo = new Edge[G.V()];distTo = new double[G.V()];marked = new boolean[G.V()];for(int v = 0;v<G.V();v++)distTo[v] = Double.POSITIVE_INFINITY;pq = new IndexMinPQ<Double>(G.V());distTo[0] = 0.0;pq.insert(0,0.0);//顶点0初始化pqwhile(!pq.isEmpty())visit(G,pq.delMin());}public void visit(EdgeWeightedGraph G,int v) {marked[v] = true;for(Edge e: G.adj(v)) {int w = e.other(v);if(marked[w]) continue;//v-w失效if(e.weight()<distTo[w]) {edgeTo[w] = e;//最佳边Edge变为edistTo[w] = e.weight();//更新distTo[]if(pq.contains(w)) pq.change(w, distTo[w]);else pq.insert(w, distTo[w]);}}}
}Prim算法的即时实现计算一个含有V个顶点和E条边的连通加权无向图的最小生成树所需空间和V成正比，所需时间和ElogV成正比（最坏情况）。
Kruskal算法：
数据结构：
- 用一条优先队列将边按照权重从小到大排序
- 用union-find算法来识别会形成环的边
- 用一条队列来保存最小生成树的所有边
Kruskal算法的计算一个含V个顶点和E条边的连通加权无向图的最小生成树所需空间与E成正比，所需时间与ElogE成正比（最坏情况）。
算法思想：
将边都添加进最小优先权队列中，每次从中取出最小的边，检查会不会与已经选出的边构成环（使用union-find算法），如果构成环，则弃掉这条边，否则将这条边加入最小生成树队列。循环执行直到最小优先权队列为空。
算法实现：
public class KruskalMST {private Queue<Edge> mst; //用来保存最小代价生成树的队列public KruskalMST(EdgeWeightedGraph G) {mst = new Queue<Edge>();MinPQ<Edge> pq = new MinPQ<Edge>(); //最小优先权队列for(Edge e: G.edges())pq.insert(e);//将所有边添加进优先队列UF uf = new UF(G.V()); //union-find算法while(!pq.isEmpty() && mst.size()<G.V()-1) {Edge e = pq.delMin();//从优先队列得到最小的边int v = e.either(),w = e.other(v);//得到最小边的顶点if(uf.connected(v, w)) continue;//判断会不会构成环uf.qu_union(v,w);//合并分量mst.enqueue(e);//将边添加进树中}}public Iterable<Edge> edges(){ return mst; }
}