/** * 该类对象可以表示图中的一条边 * @author lhever 2017年2月19日 下午5:10:49 * @version v1.0 */public class Edge implements Comparable<Edge>{ PRivate int v; private int w; private final double weight; /** * 构造 * * @param v * @param w * @param weight * @author lhever 2017年2月19日 下午5:14:30 * @since v1.0 */ public Edge(int v, int w, double weight) { if (v < 0) { throw new IllegalArgumentException("顶点v的值必须是一个非负整数"); } if (w < 0) { throw new IllegalArgumentException("顶点w的值必须是一个非负整数"); } if (Double.isNaN(weight)) { throw new IllegalArgumentException("权重不能是 NaN"); } this.v = v; this.w = w; this.weight = weight; } /** * 返回权重 * * @return * @author lhever 2017年2月19日 下午5:15:41 * @since v1.0 */ public double weight() { return weight; } /** * 返回边的其中一个顶点v * @return * @author lhever 2017年2月19日 下午5:15:54 * @since v1.0 */ public int either() { return v; } /** * 返回构成一条边的除vertex的另外一个顶点 * @param vertex * @return * @author lhever 2017年2月19日 下午5:16:16 * @since v1.0 */ public int other(int vertex) { if (vertex == v) { return w; } else if (vertex == w) { return v; } else { throw new IllegalArgumentException("不合法的顶点"); } } @Override public int compareTo(Edge other) { if (this.weight() < other.weight()) { return -1; } else if (this.weight() > other.weight()) { return 1; } else { return 0; } } public String toString() { return String.format("%d-%d %.5f", v, w, weight); } public static void main(String[] args) { Edge e = new Edge(4, 5, 78.98); System.out.println(e); }}
2 加权无向图的数据结构
import java.util.ArrayList;import java.util.List;public class EdgeWeightedGraph{ private static final String NEWLINE = System.getProperty("line.separator"); private final int V; private int E; private List<Edge>[] adj; @SuppressWarnings("unchecked") public EdgeWeightedGraph(int V) { if (V < 0) { throw new IllegalArgumentException("顶点数必须是非负数"); } this.V = V; this.E = 0; adj = (List<Edge>[]) new ArrayList[V]; for (int v = 0; v < V; v++) { adj[v] = new ArrayList<Edge>(); } } public EdgeWeightedGraph(EdgeWeightedGraph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < G.V(); v++) { List<Edge> li = new ArrayList<Edge>(); for (Edge e : G.adj[v]) { li.add(e); } for (Edge e : li) { adj[v].add(e); } } } public int V() { return V; } public int E() { return E; } private void validateVertex(int v) { if (v < 0 || v >= V) { throw new IllegalArgumentException("顶点序号 " + v + " 不在 0 和 " + (V - 1) + "之间"); } } /** * 添加边到无向非赋权图中 * * @param e * @author lhever 2017年2月19日 下午5:34:00 * @since v1.0 */ public void addEdge(Edge e) { int v = e.either(); int w = e.other(v); validateVertex(v); validateVertex(w); adj[v].add(e); adj[w].add(e); E++; } /** * 返回顶点v的临接边 * * @param v * @return * @author lhever 2017年2月19日 下午5:35:09 * @since v1.0 */ public Iterable<Edge> adj(int v) { validateVertex(v); return adj[v]; } /** * 返回顶点v的度（邻接顶点数） * * @param v * @return * @author lhever 2017年2月19日 下午5:36:08 * @since v1.0 */ public int degree(int v) { validateVertex(v); return adj[v].size(); } /** * 返回无向赋权图中的所有边 * * @return * @author lhever 2017年2月19日 下午5:38:55 * @since v1.0 */ public Iterable<Edge> edges() { List<Edge> list = new ArrayList<Edge>(); for (int v = 0; v < V; v++) { int selfLoops = 0; for (Edge e : adj(v)) { // 无向图中，同一条边会出现在这条边的两个端点的邻接列表中，此处的条件 > 目的是避免重复查找 if (e.other(v) > v) { list.add(e); } // 对于自环，比如(5, 5, 0.8),添加边的时候会添加两次，但实际上只算一条边，所以此处只添加一条 else if (e.other(v) == v) { if (selfLoops % 2 == 0) { list.add(e); } selfLoops++; } } } return list; } public String toString() { StringBuilder s = new StringBuilder(); s.append(V + " " + E + NEWLINE); for (int v = 0; v < V; v++) { s.append(v + ": "); for (Edge e : adj[v]) { s.append(e + " "); } s.append(NEWLINE); } return s.toString(); } public static void main(String[] args) { // 0——————6 // /| / | // / | / | // / 1 2 | // / | // 5———————————4 // / / // / / // / / // / / // 3 EdgeWeightedGraph g = new EdgeWeightedGraph(7); Edge e1 = new Edge(0, 1, 0.7); g.addEdge(e1); Edge e2 = new Edge(0, 2, 4.5); g.addEdge(e2); Edge e3 = new Edge(0, 5, 5.0); g.addEdge(e3); Edge e4 = new Edge(0, 6, 3.1); g.addEdge(e4); Edge e5 = new Edge(5, 4, 2.9); g.addEdge(e5); Edge e6 = new Edge(6, 4, 7.8); g.addEdge(e6); Edge e7 = new Edge(3, 4, 9.7); g.addEdge(e7); Edge e8 = new Edge(3, 5, 6.0); g.addEdge(e8); System.out.println(g); EdgeWeightedGraph g1 = new EdgeWeightedGraph(g); System.out.println(g1); }}
3 prim算法的延迟实现（添加新的横切边到树中的时候才能识别出失效的边）
import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;/** * 求无向非赋权图最小生成树的prim算法（延迟实现） * @author xxx 2017年2月19日 下午6:20:21 * @version v1.0 */public class LazyPrimMST{ private static final double FLOATING_POINT_EPSILON = 1E-12; private double weight; // 最小生成树的权重 private List<Edge> mst; // 最小生成树的所有边 private boolean[] marked; // 如果顶点v已经被加入到最小生成树中， 则marked[v] = true private PriorityQueue<Edge> pq; public LazyPrimMST(EdgeWeightedGraph G) { mst = new ArrayList<Edge>(); pq = new PriorityQueue<Edge>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) { if (!marked[v]) { prim(G, v); } } assert check(G); } private void prim(EdgeWeightedGraph G, int s) { scan(G, s); while (!pq.isEmpty()) { // 当最小生成树含有v- 1 条边的时候最好停止 // 取出权值最小的边 Edge e = pq.poll(); int v = e.either(), w = e.other(v); assert marked[v] || marked[w]; if (marked[v] && marked[w]) { continue; } mst.add(e); // 边e属于最小生成树的边 weight += e.weight(); // 在运算过程中，最小生成树是逐渐生成的，此处将v添加到当前最小树中 if (!marked[v]) { scan(G, v); } // 在运算过程中，最小生成树是逐渐生成的，此处将v添加到当前最小树中 if (!marked[w]) { scan(G, w); } } } /** * 将顶点v的所有满足条件的邻接边添加到优先队列中， * 条件是： 这些邻接边的另外一个顶点还没有添加到当前的最小生成树中（还未被访问） * @param G * @param v * @author xxx 2017年2月19日 下午6:27:26 * @since v1.0 */ private void scan(EdgeWeightedGraph G, int v) { assert !marked[v]; marked[v] = true; for (Edge e : G.adj(v)) { if (!marked[e.other(v)]) { pq.add(e); } } } public Iterable<Edge> edges() { return mst; } public double weight() { return weight; } private boolean check(EdgeWeightedGraph G) { // 验证权重是否一致 double totalWeight = 0.0; for (Edge e : edges()) { totalWeight += e.weight(); } if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) { System.err.printf("最小生成树的所有边的权值之和与 weight()方法计算的结果不一致: %f vs. %f/n", totalWeight, weight()); return false; } // 利用连通查找算法判断是否是无环图 UnionFind UnionFind = new UnionFind(G.V()); for (Edge e : edges()) { int v = e.either(), w = e.other(v); if (UnionFind.connected(v, w)) { System.err.println("不是一个树森林"); return false; } UnionFind.union(v, w); } // 判断是否是一颗生成树 for (Edge e : G.edges()) { int v = e.either(), w = e.other(v); if (!UnionFind.connected(v, w)) { System.err.println("不是一棵生成树"); return false; } } // 判断是否是一棵最小生成树 for (Edge e : edges()) { // 最小生成树中除e以外的所有边 UnionFind = new UnionFind(G.V()); for (Edge f : mst) { int x = f.either(), y = f.other(x); if (f != e) { UnionFind.union(x, y); } } // check that e is min weight edge in crossing cut for (Edge f : G.edges()) { int x = f.either(), y = f.other(x); if (!UnionFind.connected(x, y)) { if (f.weight() < e.weight()) { System.err.println("边 " + f + "违背了切分条件"); return false; } } } } return true; } public static void main(String[] args) { // 0——————6 // /| / | // / | / | // / 1 2 | // / | // 5———————————4 // / / // / / // / / // / / // 3 EdgeWeightedGraph g = new EdgeWeightedGraph(7); Edge e1 = new Edge(0, 1, 0.7); g.addEdge(e1); Edge e2 = new Edge(0, 2, 4.5); g.addEdge(e2); Edge e3 = new Edge(0, 5, 5.0); g.addEdge(e3); Edge e4 = new Edge(0, 6, 3.1); g.addEdge(e4); Edge e5 = new Edge(5, 4, 2.9); g.addEdge(e5); Edge e6 = new Edge(6, 4, 7.8); g.addEdge(e6); Edge e7 = new Edge(3, 4, 9.7); g.addEdge(e7); Edge e8 = new Edge(3, 5, 6.0); g.addEdge(e8); LazyPrimMST mst = new LazyPrimMST(g); for (Edge e : mst.edges()) { System.out.println(e); } System.out.printf("%.5f/n", mst.weight()); }}///////////////////算法中用于连通查找的类的代码如下///////////////////////////import java.util.Arrays;public class UnionFind { private int[] parent; // parent[i]的值为节点 i的父节点（或根节点） private byte[] rank; // rank[i]的值为以i为根节点的子树的秩 private int count; // 连通分量数 /** * 初始化一个连通-查找算法的数据结构，N表示该数据结构中的节点（或称顶点、或称触电），并且，刚初始化 * 的数据结构中，各个节点都位于各自的连通分量当中，也即N个连通分量 * @param N * @author xxx 2017年2月28日 上午12:14:48 * @since v1.0 */ public UnionFind(int N) { if (N < 0) { throw new IllegalArgumentException(); } count = N; parent = new int[N]; rank = new byte[N]; for (int i = 0; i < N; i++) { parent[i] = i; rank[i] = 0; } } /** * 返回包含节点p的连通分量的id（或者是identifier） * @param p * @return * @author xxx 2017年2月28日 上午12:26:19 * @since v1.0 */ public int find(int p) { validate(p); while (p != parent[p]) { parent[p] = parent[parent[p]]; // 路径压缩 p = parent[p]; } return p; } /** * 返回连通分量的总数 * @return * @author xxx 2017年2月28日 上午12:21:16 * @since v1.0 */ public int count() { return count; } /** * 如果节点p和节点q位于同一个连通分量中，则返回true * @param p * @param q * @return * @author xxx 2017年2月28日 上午12:20:35 * @since v1.0 */ public boolean connected(int p, int q) { return find(p) == find(q); } /** * 将包含节点p的连通分量与包含节点q的连通分量合并 * @param p * @param q * @author xxx 2017年2月28日 上午12:19:24 * @since v1.0 */ public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) { return; } // make root of smaller rank point to root of larger rank if (rank[rootP] < rank[rootQ]) { parent[rootP] = rootQ; } else if (rank[rootP] > rank[rootQ]) { parent[rootQ] = rootP; } else { parent[rootQ] = rootP; rank[rootP]++; } count--;//合并之后连通分量减一 } private void validate(int p) { int N = parent.length; if (p < 0 || p >= N) { throw new IndexOutOfBoundsException("节点的大小必须位于0和 " + (N - 1) + "之间"); } } public static void main(String[] args) { UnionFind uf = new UnionFind(4); if(!uf.connected(0, 3)) { uf.union(0, 3); } System.out.println(0 + " " + 3); System.out.println(uf.count() + " components"); if(!uf.connected(0, 2)) { uf.union(0, 2); } System.out.println(0 + " " + 2); System.out.println(uf.count() + " components"); System.out.println(Arrays.toString(uf.parent)); }}
4 Prim算法的即时实现
import java.util.ArrayList;import java.util.List;/** * 无向非赋权图的最小生成树算法 * @author xxx 2017年2月19日 下午7:43:11 * @version v1.0 */public class PrimMST { private static final double FLOATING_POINT_EPSILON = 1E-12; private Edge[] edgeTo; private double[] distTo; private boolean[] marked; private IndexMinPQ<Double> pq; public PrimMST(EdgeWeightedGraph G) { edgeTo = new Edge[G.V()]; distTo = new double[G.V()]; marked = new boolean[G.V()]; pq = new IndexMinPQ<Double>(G.V()); for (int v = 0; v < G.V(); v++) { distTo[v] = Double.POSITIVE_INFINITY; } for (int v = 0; v < G.V(); v++) { if (!marked[v]) { prim(G, v); } } assert check(G); } private void prim(EdgeWeightedGraph G, int s) { distTo[s] = 0.0; pq.insert(s, distTo[s]); while (!pq.isEmpty()) { int v = pq.delMin(); scan(G, v); } } private void scan(EdgeWeightedGraph G, int v) { marked[v] = true; for (Edge e : G.adj(v)) { int w = e.other(v); if (marked[w]) { continue; // v-w is obsolete edge } if (e.weight() < distTo[w]) { distTo[w] = e.weight(); edgeTo[w] = e; if (pq.contains(w)) { pq.decreaseKey(w, distTo[w]); } else { pq.insert(w, distTo[w]); } } } } public Iterable<Edge> edges() { List<Edge> mst = new ArrayList<Edge>(); for (int v = 0; v < edgeTo.length; v++) { Edge e = edgeTo[v]; if (e != null) { mst.add(e); } } return mst; } public double weight() { double weight = 0.0; for (Edge e : edges()) { weight += e.weight(); } return weight; } private boolean check(EdgeWeightedGraph G) { double totalWeight = 0.0; for (Edge e : edges()) { totalWeight += e.weight(); } if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) { System.err.printf("最小生成树中所有边的权值和与weight()方法计算结果不一致"); return false; } UnionFind UnionFind = new UnionFind(G.V()); for (Edge e : edges()) { int v = e.either(), w = e.other(v); if (UnionFind.connected(v, w)) { System.err.println("不是一个树森林"); return false; } UnionFind.union(v, w); } for (Edge e : G.edges()) { int v = e.either(), w = e.other(v); if (!UnionFind.connected(v, w)) { System.err.println("不是最小生成树"); return false; } } for (Edge e : edges()) { UnionFind = new UnionFind(G.V()); for (Edge f : edges()) { int x = f.either(), y = f.other(x); if (f != e) { UnionFind.union(x, y); } } for (Edge f : G.edges()) { int x = f.either(), y = f.other(x); if (!UnionFind.connected(x, y)) { if (f.weight() < e.weight()) { System.err.println("边 " + f + " 违背了切分定理"); return false; } } } } return true; } public static void main(String[] args) { // 0——————6 // /| / | // / | / | // / 1 2 | // / | // 5———————————4 // / / // / / // / / // / / // 3 EdgeWeightedGraph g = new EdgeWeightedGraph(7); Edge e1 = new Edge(0, 1, 0.7); g.addEdge(e1); Edge e2 = new Edge(0, 2, 4.5); g.addEdge(e2); Edge e3 = new Edge(0, 5, 5.0); g.addEdge(e3); Edge e4 = new Edge(0, 6, 3.1); g.addEdge(e4); Edge e5 = new Edge(5, 4, 2.9); g.addEdge(e5); Edge e6 = new Edge(6, 4, 7.8); g.addEdge(e6); Edge e7 = new Edge(3, 4, 9.7); g.addEdge(e7); Edge e8 = new Edge(3, 5, 6.0); g.addEdge(e8); PrimMST mst = new PrimMST(g); for (Edge e : mst.edges()) { System.out.println(e); } System.out.printf("%.5f/n", mst.weight()); }}///////////////////算法中使用到的IndexMinPQ.java代码如下//////////////////////import java.util.Iterator;import java.util.NoSuchElementException;/** * The <tt>IndexMinPQ</tt> class represents an indexed priority queue of generic keys. * It supports the usual <em>insert</em> and <em>delete-the-minimum</em> * Operations, along with <em>delete</em> and <em>change-the-key</em> * methods. In order to let the client refer to keys on the priority queue, * an integer between 0 and maxN-1 is associated with each key—the client * uses this integer to specify which key to delete or change. * It also supports methods for peeking at the minimum key, * testing if the priority queue is empty, and iterating through * the keys. * <p> * This implementation uses a binary heap along with an array to associate * keys with integers in the given range. * The <em>insert</em>, <em>delete-the-minimum</em>, <em>delete</em>, * <em>change-key</em>, <em>decrease-key</em>, and <em>increase-key</em> * operations take logarithmic time. * The <em>is-empty</em>, <em>size</em>, <em>min-index</em>, <em>min-key</em>, and <em>key-of</em> * operations take constant time. * Construction takes time proportional to the specified capacity. * <p> * For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne * * @param <Key> the generic type of key on this priority queue */public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> { private int maxN; // maximum number of elements on PQ private int N; // number of elements on PQ private int[] pq; // binary heap using 1-based indexing private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i private Key[] keys; // keys[i] = priority of i /** * Initializes an empty indexed priority queue with indices between <tt>0</tt> * and <tt>maxN - 1</tt>. * @param maxN the keys on this priority queue are index from <tt>0</tt> * <tt>maxN - 1</tt> * @throws IllegalArgumentException if <tt>maxN</tt> < <tt>0</tt> */ public IndexMinPQ(int maxN) { if (maxN < 0) throw new IllegalArgumentException(); this.maxN = maxN; keys = (Key[]) new Comparable[maxN + 1]; // make this of length maxN?? pq = new int[maxN + 1]; qp = new int[maxN + 1]; // make this of length maxN?? for (int i = 0; i <= maxN; i++) qp[i] = -1; } /** * Returns true if this priority queue is empty. * * @return <tt>true</tt> if this priority queue is empty; * <tt>false</tt> otherwise */ public boolean isEmpty() { return N == 0; } /** * Is <tt>i</tt> an index on this priority queue? * * @param i an index * @return <tt>true</tt> if <tt>i</tt> is an index on this priority queue; * <tt>false</tt> otherwise * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> */ public boolean contains(int i) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); return qp[i] != -1; } /** * Returns the number of keys on this priority queue. * * @return the number of keys on this priority queue */ public int size() { return N; } /** * Associates key with index <tt>i</tt>. * * @param i an index * @param key the key to associate with index <tt>i</tt> * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @throws IllegalArgumentException if there already is an item associated * with index <tt>i</tt> */ public void insert(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue"); N++; qp[i] = N; pq[N] = i; keys[i] = key; swim(N); } /** * Returns an index associated with a minimum key. * * @return an index associated with a minimum key * @throws NoSuchElementException if this priority queue is empty */ public int minIndex() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } /** * Returns a minimum key. * * @return a minimum key * @throws NoSuchElementException if this priority queue is empty */ public Key minKey() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); return keys[pq[1]]; } /** * Removes a minimum key and returns its associated index. * @return an index associated with a minimum key * @throws NoSuchElementException if this priority queue is empty */ public int delMin() { if (N == 0) throw new NoSuchElementException("Priority queue underflow"); int min = pq[1]; exch(1, N--); sink(1); assert min == pq[N+1]; qp[min] = -1; // delete keys[min] = null; // to help with garbage collection pq[N+1] = -1; // not needed return min; } /** * Returns the key associated with index <tt>i</tt>. * * @param i the index of the key to return * @return the key associated with index <tt>i</tt> * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @throws NoSuchElementException no key is associated with index <tt>i</tt> */ public Key keyOf(int i) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); else return keys[i]; } /** * Change the key associated with index <tt>i</tt> to the specified value. * * @param i the index of the key to change * @param key change the key associated with index <tt>i</tt> to this key * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @throws NoSuchElementException no key is associated with index <tt>i</tt> */ public void changeKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); keys[i] = key; swim(qp[i]); sink(qp[i]); } /** * Change the key associated with index <tt>i</tt> to the specified value. * * @param i the index of the key to change * @param key change the key associated with index <tt>i</tt> to this key * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @deprecated Replaced by {@link #changeKey(int, Key)}. */ public void change(int i, Key key) { changeKey(i, key); } /** * Decrease the key associated with index <tt>i</tt> to the specified value. * * @param i the index of the key to decrease * @param key decrease the key associated with index <tt>i</tt> to this key * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @throws IllegalArgumentException if key ≥ key associated with index <tt>i</tt> * @throws NoSuchElementException no key is associated with index <tt>i</tt> */ public void decreaseKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key"); keys[i] = key; swim(qp[i]); } /** * Increase the key associated with index <tt>i</tt> to the specified value. * * @param i the index of the key to increase * @param key increase the key associated with index <tt>i</tt> to this key * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @throws IllegalArgumentException if key ≤ key associated with index <tt>i</tt> * @throws NoSuchElementException no key is associated with index <tt>i</tt> */ public void increaseKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key"); keys[i] = key; sink(qp[i]); } /** * Remove the key associated with index <tt>i</tt>. * * @param i the index of the key to remove * @throws IndexOutOfBoundsException unless 0 ≤ <tt>i</tt> < <tt>maxN</tt> * @throws NoSuchElementException no key is associated with index <t>i</tt> */ public void delete(int i) { if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); int index = qp[i]; exch(index, N--); swim(index); sink(index); keys[i] = null; qp[i] = -1; } /*************************************************************************** * General helper functions. ***************************************************************************/ private boolean greater(int i, int j) { return keys[pq[i]].compareTo(keys[pq[j]]) > 0; } private void exch(int i, int j) { int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; qp[pq[i]] = i; qp[pq[j]] = j; } /*************************************************************************** * Heap helper functions. ***************************************************************************/ private void swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= N) { int j = 2*k; if (j < N && greater(j, j+1)) j++; if (!greater(k, j)) break; exch(k, j); k = j; } } /*************************************************************************** * Iterators. ***************************************************************************/ /** * Returns an iterator that iterates over the keys on the * priority queue in ascending order. * The iterator doesn't implement <tt>remove()</tt> since it's optional. * * @return an iterator that iterates over the keys in ascending order */ public Iterator<Integer> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Integer> { // create a new pq private IndexMinPQ<Key> copy; // add all elements to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { copy = new IndexMinPQ<Key>(pq.length - 1); for (int i = 1; i <= N; i++) copy.insert(pq[i], keys[pq[i]]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Integer next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMin(); } } /** * Unit tests the <tt>IndexMinPQ</tt> data type. */ public static void main(String[] args) { // insert a bunch of strings String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" }; IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length); for (int i = 0; i < strings.length; i++) { pq.insert(i, strings[i]); } // delete and print each key while (!pq.isEmpty()) { int i = pq.delMin(); StdOut.println(i + " " + strings[i]); } StdOut.println(); // reinsert the same strings for (int i = 0; i < strings.length; i++) { pq.insert(i, strings[i]); } // print each key using the iterator for (int i : pq) { StdOut.println(i + " " + strings[i]); } while (!pq.isEmpty()) { pq.delMin(); } }}/****************************************************************************** * Copyright 2002-2015, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/
5 另外一个联通查找算法的代码(后续用于Kruskal算法)
import java.util.Arrays;import java.util.HashSet;import java.util.Set;public class SetBasedUnionFind { private int count; // 连通分量数 private Set<Integer>[] components; private int N; @SuppressWarnings("unchecked") public SetBasedUnionFind(int N) { if (N <= 0) { throw new IllegalArgumentException(); } this.N = N; this.count = N; components = new Set[N]; } public boolean connected(Integer i, Integer j) { if (components[i] != null && components[j] != null && components[i] == components[j]) { return true; } return false; } public void union(Integer i, Integer j) { validate(i); validate(j); Set<Integer> setI=components[i]; Set<Integer> setJ=components[j]; //边的两个顶点都未出现在其他集合中 if(setI == null && setJ == null) { Set<Integer> set=new HashSet<Integer>(); set.add(i); set.add(j); components[i] = set; components[j] = set; }//有一个顶点在其他集合中，一个不在，将不在的那个顶点集合合并进去 else if(setI == null && setJ != null) { components[i] = setJ; setJ.add(i); } else if(setI != null && setJ == null) { components[j] = setI; setI.add(j); }//分别在不同的集合中，合并两个集合 else if(setI != setJ) { for(int k: setI) { components[k] = setJ; } setJ.addAll(setI); } else {}//两个顶点在同一个结合中，会出现环路，舍弃 count--; } public int count() { return count; } private void validate(Integer p) { if(p < 0 || p >= this.N) { throw new IllegalArgumentException(); } } public static void main(String... args) { SetBasedUnionFind uf = new SetBasedUnionFind(5); System.out.println(uf.count()); System.out.println(uf.connected(0, 4)); uf.getAllComponents(); uf.union(0, 4); System.out.println(uf.count()); System.out.println(uf.connected(0, 4)); uf.getAllComponents(); uf.union(0, 3); System.out.println(uf.count()); System.out.println(uf.connected(0, 3)); uf.getAllComponents(); uf.union(1, 2); System.out.println(uf.count()); System.out.println(uf.connected(1, 2)); System.out.println(uf.connected(1, 0)); uf.getAllComponents(); uf.union(1, 4); System.out.println(uf.count()); System.out.println(uf.connected(4, 2)); uf.getAllComponents(); } public Set[] getAllComponents() { Set<Set<Integer>> result = new HashSet<Set<Integer>>(); for(int i = 0; i < components.length; i++) { if(components[i] == null) { Set<Integer> set = new HashSet<Integer>(); set.add(i); result.add(set); } else { result.add(components[i]); } } @SuppressWarnings("unchecked") Set<Integer>[] array = (Set[]) result.toArray(new HashSet[result.size()]); System.out.println(Arrays.toString(array)); return array; }/////////////////////////该算法的改进版//////////////////////////////////////import java.util.Arrays;import java.util.HashSet;import java.util.Set;public class SetBasedUnionFind2 { private int count; // 连通分量数 private Set<Integer>[] components; private int N; @SuppressWarnings("unchecked") public SetBasedUnionFind2(int N) { if (N <= 0) { throw new IllegalArgumentException(); } this.N = N; this.count = N; components = new Set[N]; for(int i = 0; i < components.length; i++) { components[i] = new HashSet<Integer>(); components[i].add(i); } } public boolean connected(Integer i, Integer j) { if (components[i] == components[j]) { return true; } return false; } public void union(Integer i, Integer j) { validate(i); validate(j); Set<Integer> setI=components[i]; Set<Integer> setJ=components[j]; if(setI != setJ) { for(int k: setI) { components[k] = setJ; } setJ.addAll(setI); } else {}//两个顶点在同一个结合中，会出现环路，舍弃 count--; } public int count() { return count; } private void validate(Integer p) { if(p < 0 || p >= this.N) { throw new IllegalArgumentException(); } } @SuppressWarnings("unchecked") public Set[] getAllComponents() { Set<Set<Integer>> result = new HashSet<Set<Integer>>(); for(int i = 0; i < components.length; i++) { result.add(components[i]); } Set<Integer>[] array = (Set[]) result.toArray(new HashSet[result.size()]); System.out.println(Arrays.toString(array)); return array; } public static void main(String... args) { SetBasedUnionFind2 uf = new SetBasedUnionFind2(5); System.out.println(uf.count()); System.out.println(uf.connected(0, 4)); uf.getAllComponents(); uf.union(0, 4); System.out.println(uf.count()); System.out.println(uf.connected(0, 4)); uf.getAllComponents(); uf.union(0, 3); System.out.println(uf.count()); System.out.println(uf.connected(0, 3)); uf.getAllComponents(); uf.union(1, 2); System.out.println(uf.count()); System.out.println(uf.connected(1, 2)); System.out.println(uf.connected(2, 3)); uf.getAllComponents(); uf.union(1, 4); System.out.println(uf.count()); System.out.println(uf.connected(4, 2)); uf.getAllComponents(); }}
6 Kruskal算法的具体实现
import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;import edu.princeton.cs.algs4.UF;/** * 无向赋权图最小生成树的Kruskal算法 * @author xxx 2017年2月19日 下午9:08:59 * @version v1.0 */public class KruskalMST{ private static final double FLOATING_POINT_EPSILON = 1E-12; private double weight; private List<Edge> mst = new ArrayList<Edge>(); public KruskalMST(EdgeWeightedGraph G) { PriorityQueue<Edge> pq = new PriorityQueue<Edge>(); for (Edge e : G.edges()) { pq.add(e); } UF uf = new UF(G.V()); while (!pq.isEmpty() && mst.size() < G.V() - 1) { Edge e = pq.poll(); int v = e.either(); int w = e.other(v); if (!uf.connected(v, w)) { uf.union(v, w); mst.add(e); weight += e.weight(); } } assert check(G); } /** * 返回最小生成树中的所有边 * @return * @author xxx 2017年2月19日 下午9:09:37 * @since v1.0 */ public Iterable<Edge> edges() { return mst; } /** * 返回最小生成树的权值 * @return * @author xxx 2017年2月19日 下午9:10:10 * @since v1.0 */ public double weight() { return weight; } private boolean check(EdgeWeightedGraph G) { double total = 0.0; for (Edge e : edges()) { total += e.weight(); } if (Math.abs(total - weight()) > FLOATING_POINT_EPSILON) { System.err.printf("最小生成树的所有边的权值和与weight()方法计算的结果不一致"); return false; } // 验证最小生成树中是否含有环 UF uf = new UF(G.V()); for (Edge e : edges()) { int v = e.either(), w = e.other(v); if (uf.connected(v, w)) { System.err.println("不是一个数森林"); return false; } uf.union(v, w); } // 验证是否是一个生成树 for (Edge e : G.edges()) { int v = e.either(), w = e.other(v); if (!uf.connected(v, w)) { System.err.println("不是一棵生成树"); return false; } } for (Edge e : edges()) { uf = new UF(G.V()); for (Edge f : mst) { int x = f.either(), y = f.other(x); if (f != e) uf.union(x, y); } for (Edge f : G.edges()) { int x = f.either(), y = f.other(x); if (!uf.connected(x, y)) { if (f.weight() < e.weight()) { System.err.println("边 " + f + " 违背了切分定理"); return false; } } } } return true; } public static void main(String[] args) { EdgeWeightedGraph g = new EdgeWeightedGraph(7); Edge e1 = new Edge(0, 1, 0.7); g.addEdge(e1); Edge e2 = new Edge(0, 2, 4.5); g.addEdge(e2); Edge e3 = new Edge(0, 5, 5.0); g.addEdge(e3); Edge e4 = new Edge(0, 6, 3.1); g.addEdge(e4); Edge e5 = new Edge(5, 4, 2.9); g.addEdge(e5); Edge e6 = new Edge(6, 4, 7.8); g.addEdge(e6); Edge e7 = new Edge(3, 4, 9.7); g.addEdge(e7); Edge e8 = new Edge(3, 5, 6.0); g.addEdge(e8); KruskalMST mst = new KruskalMST(g); for (Edge e : mst.edges()) { System.out.println(e); } System.out.printf("%.5f/n", mst.weight()); }}
7 Kruskal算法的另外一种实现
import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;/** * 最小生成树的Kruskal算法，该类使用矩阵结构表示图 * @author lhever 2017年2月28日 下午11:32:49 * @version v1.0 */public class MatrixBasedKruskalMST{ private double weight = 0;// 权重 private List<Edge> mst = new ArrayList<Edge>();// 最小生成树的所有边 /** * 构造，在构造中完成计算 * * @param graph * @author lhever 2017年2月28日 下午11:34:01 * @since v1.0 */ public MatrixBasedKruskalMST(double[][] graph) { int row = graph.length; int col = graph[0].length; if (row != col) { throw new IllegalArgumentException("传入的二维数组行值和列值必须相等"); } int count = 0; PriorityQueue<Edge> edgeList = getEdgeList(graph); SetBasedUnionFind2 uf = new SetBasedUnionFind2(row); while (count < row - 1 && !edgeList.isEmpty()) { Edge e = edgeList.poll(); int v = e.either(); int u = e.other(v); if (!uf.connected(v, u)) { uf.union(v, u); mst.add(e); weight += e.weight(); count++; } } } /** * 获取最小生成树的所有边 * @return * @author lhever 2017年2月28日 下午11:48:57 * @since v1.0 */ public List<Edge> edges() { return mst; } public double weight() { return weight; } /** * 获取图中的所有边 * @param graph * @return * @author lhever 2017年2月28日 下午11:49:33 * @since v1.0 */ private static PriorityQueue<Edge> getEdgeList(double[][] graph) { PriorityQueue<Edge> edgeList = new PriorityQueue<Edge>(); int rlength = graph.length; int clength = graph[0].length; for (int i = 0; i < rlength; i++) { for (int j = i + 1; j < clength; j++) { if (graph[i][j] > 0 & graph[i][j] < Double.MAX_VALUE) { Edge e = new Edge(i, j, graph[i][j]); edgeList.add(e); } } } return edgeList; } public static void main(String[] args) { double graph[][] = { { 0, 1, 4, 4, 5 }, { 1, 0, 3, 7, 5 }, { 4, 3, 0, 6, Double.MAX_VALUE }, { 4, 7, 6, 0, 2 }, { 5, 5, Double.MAX_VALUE, 2, 0 } }; MatrixBasedKruskalMST mst = new MatrixBasedKruskalMST(graph); List<Edge> edgeList = mst.edges(); for (Edge e : edgeList) { System.out.println(e); } System.out.println("-------------------------------------------");// 原图表示为如下结构 // ① // / | / // 6 1 5 // / | / // ②---5--③--5--④ // / / / / // 3 6 4 2 // // // // ⑤--6----⑥ double m = Double.MAX_VALUE; double[][] weight = {{0, 0, 0, 0, 0, 0, 0}, {0, m, 6, 1, 5, m, m}, {0, 6, m, 5, m, 3, m}, {0, 1, 5, m, 5, 6, 4}, {0, 5, m, 5, m, m, 2}, {0, m, 3, 6, m, m, 6}, {0, m, m, 4, 2, 6, m}};//上图的矩阵 MatrixBasedKruskalMST mst1 = new MatrixBasedKruskalMST(weight); //最小生成树为： // ① // | // 1 // | // ②---5---③ ④ // / | / // 3 4 2 // / | / // / | / // ⑤ ⑥ // List<Edge> edgeList1 = mst1.edges(); for (Edge e : edgeList1) { System.out.println(e); } }}
