每日一省之————加權無向圖的最小生成樹演算法(Prim/Kruskal演算法)

NO IMAGE

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);
}
// 對於自環,比如(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&mdash;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> &lt; <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 &le; <tt>i</tt> &lt; <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 &le; <tt>i</tt> &lt; <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 &le; <tt>i</tt> &lt; <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 &le; <tt>i</tt> &lt; <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 &le; <tt>i</tt> &lt; <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 &le; <tt>i</tt> &lt; <tt>maxN</tt>
* @throws IllegalArgumentException if key &ge; 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 &le; <tt>i</tt> &lt; <tt>maxN</tt>
* @throws IllegalArgumentException if key &le; 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 &le; <tt>i</tt> &lt; <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);
}
}
}