1.带权重的边的数据结构
/**
* 该类对象可以表示图中的一条边
* @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);
}
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)
{
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;
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())
{
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);
weight += e.weight();
if (!marked[v])
{
scan(G, 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())
{
UnionFind = new UnionFind(G.V());
for (Edge f : mst)
{
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)
{
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;
private byte[] rank;
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;
}
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;
}
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)
{
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());
}
}
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;
private int N;
private int[] pq;
private int[] qp;
private Key[] keys;
/**
* 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];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
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;
keys[min] = null;
pq[N+1] = -1;
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> {
private IndexMinPQ<Key> copy;
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) {
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]);
}
while (!pq.isEmpty()) {
int i = pq.delMin();
StdOut.println(i + " " + strings[i]);
}
StdOut.println();
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}
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("-------------------------------------------");
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);
List<Edge> edgeList1 = mst1.edges();
for (Edge e : edgeList1)
{
System.out.println(e);
}
}
}
