最小生成树的Prim算法
2018-04-17 本文已影响63人
SharryChoo
Prim算法
- 特点: Prim 算法能够得到任意加权图的最小生成树
- 使用到的数据结构
- 延时版本: 优先队列
- 即时版本: 索引优先队列
优先队列
-
定义: 许多应用程序都需要处理有序的元素, 但不一定要求它们全部有序, 或是不一定要一次就将它们排序, 很多情况下, 我们会收集一些元素, 处理当前键值最大的元素, 然后再收集一些元素, 再处理当前键值最大的元素
在这种情况下, 一个适合的数据结构应该支持两种操作: 删除最大/最小元素 和 插入元素, 这种数据类型叫做优先队列 -
实现方案
- 数组: 有序, 无序
- 链表: 有序, 无序
- 二叉堆: 通过堆有序可以很容易的获得最大元素, 并且元素也不是绝对有序的, 最适合实现优先队列
-
具体实现
/**
* 优先队列(二叉堆实现)
* @author Frank
*/
@SuppressWarnings("unchecked")
public class PriorityQueue<Key extends Comparable<Key>> implements Iterable<Key>{
public enum Type{
Maximum,// 最大优先
Minimum // 最小优先
}
private Type type;
private Key[] heap;
private int N = 0;// 存储于 heap[1...N] 中, heap[0] 没有使用
public PriorityQueue(Type type, int maxN) {
this.type = type;
heap = (Key[]) new Comparable[maxN + 1];
}
/**
* 向优先队列中插入一个元素
*/
public void insert(Key v){
heap[++N] = v;
// 对新添加的元素进行上浮排序
swim(N);
}
/**
* 获取堆顶元素(最大/或者最小的元素)
*/
public Key top(){
return heap[1];
}
/**
* 删除并返回(最小/最大)元素
*/
public Key delTop(){
// 从根结点获取堆顶元素
Key min = heap[1];
// 将其和最后一个结点元素互换
exch(1, N--);
// 将刚才互换到底部的元素置空
heap[N+1] = null;
// 下沉到合适的位置
sink(1);
return min;
}
/**
* 返回队列是否为空
*/
public boolean isEmpty(){
return N == 0;
}
/**
* 返回优先队列中元素的个数
*/
public int size(){
return N;
}
/**
* 比较元素大小
*/
private boolean less(int i, int j) {
return heap[i].compareTo(heap[j]) < 0;
}
/**
* 交换元素位置
*/
private void exch(int i, int j) {
Key t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
/**
* 元素上浮, 实现堆序列
*/
private void swim(int k) {
while (k > 1 && (type == Type.Maximum
? less(k/2, k) : !less(k/2, k))) {
exch(k/2, k);
k = k/2;
}
}
/**
* 元素下沉, 实现堆序列
*/
private void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N &&(type == Type.Maximum
? less(j, j + 1) : !less(j, j + 1))) j++;
if (type == Type.Maximum
? !less(k, j) : less(k, j)) break;
exch(k, j);
k = j;
}
}
@Override
public Iterator<Key> iterator() {
return new Iterator<Key>() {
int index = 0;
@Override
public boolean hasNext() {
return index < N;
}
@Override
public Key next() {
return heap[++index];
}
};
}
}
索引优先队列
1.优先队列存在的问题: 优先队列有一个缺点，就是不能直接访问已存在于优先队列中的对象，并更新它们。这个问题在 Prim 算法的及时实现中就有明显的体现。
2. 定义: 索引优先队用一个整数和对象进行关联，当我们需要更新该对象的值时，可以通这个整数进行快速索引，然后对对象的值进行更新。当然更新后的对象在优先队列中的位置可能发生变化，这样以保证整个队列还是一个优先队列。
3.1 使用纯数组实现
互逆数组实现索引优先队列.jpg
/**
* 索引最优先队列(数组实现)
* @author Frank
*/
@SuppressWarnings("unchecked")
public class IndexArrayPriorityQueue<Element extends Comparable<Element>> {
public enum Type{
Maximum,// 最大优先
Minimum // 最小优先
}
private Type type;
private int N;
private Element[] elements;// 值的二叉堆, 索引为对应的 k值, 不连续存放
private int[] pq;// Key 的数组, 连续存放存放对应的 key
private int[] qp;// 索引的数组, 存放 key 在 pq 中的索引
public IndexArrayPriorityQueue(Type type, int maxN) {
this.type = type;
elements = (Element[])new Comparable[maxN + 1];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
// 初始化索引数组, 索引默认为 -1
for (int i = 0; i <= maxN; i++) qp[i] = -1;
}
public boolean isEmpty() {
return N == 0;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int key, Element element) {
N++;
pq[N] = key;// pq 的第 N 个位置存放 k
qp[key] = N;// qp 记录 key 的索引
elements[key] = element;
// 因为是新插入的, 所以默认在最底部,
// 执行上浮操作即可保证堆序列
swim(N);
}
public int topKey() {
return pq[1];
}
public Element topElement() {
return elements[pq[1]];
}
public int delTop() {
int key = pq[1];
delete(key);
return key;
}
public void change(int k, Element key) {
elements[k] = key;
// 重构堆序列
swim(qp[k]);
sink(qp[k]);
}
public void delete(int key) {
int keyIndex = qp[key];
// 与最后一个元素互换
exch(keyIndex, N--);
// 重构堆序列
swim(keyIndex);
sink(keyIndex);
// 释放数组对应位置废弃的值
elements[key] = null;
qp[key] = -1;
}
/**
* 元素上浮, 实现堆序列
*/
private void swim(int k) {
while (k > 1 && (type == Type.Maximum
? less(k/2, k) : !less(k/2, k))) {
exch(k/2, k);
k = k/2;
}
}
/**
* 元素下沉, 实现堆序列
*/
private void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N &&(type == Type.Maximum
? less(j, j + 1) : !less(j, j + 1))) j++;
if (type == Type.Maximum
? !less(k, j) : less(k, j)) break;
exch(k, j);
k = j;
}
}
/**
* 比较大小(堆序列的位置)
*/
private boolean less(int i, int j) {
return elements[pq[i]].compareTo(elements[pq[j]]) < 0;
}
/**
* 交换元素位置(堆序列的位置)
*/
private void exch(int i, int j) {
// exchange key array
int tempKey = pq[i];
pq[i] = pq[j];
pq[j] = tempKey;
// exchange keyIndex array
qp[pq[i]] = i;
qp[pq[j]] = j;
}
}
3.2 定义 Entry 实体类实现
/**
* 索引最优先队列(使用Entry实现)
* @author Frank
*/
@SuppressWarnings("unchecked")
public class IndexEntryPriorityQueue<Element extends Comparable<Element>> {
public enum Type{
Maximum,// 最大优先
Minimum // 最小优先
}
private Type type;
private int N;
private int[] qp;// 记录key在堆中的索引
private Entry<Integer, Element>[] heap;// 堆序列
public IndexEntryPriorityQueue(Type type, int maxN) {
this.type = type;
heap = new Entry[maxN + 1];
qp = new int[maxN + 1];
// 初始化索引数组, 索引默认为 -1
for (int i = 0; i <= maxN; i++) qp[i] = -1;
}
public boolean isEmpty() {
return N == 0;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int key, Element element) {
N++;
heap[N] = new Entry<Integer, Element>(key, element);
qp[key] = N;// qp 记录 key 的索引
// 因为是新插入的, 所以默认在最底部,
// 执行上浮操作即可保证堆序列
swim(N);
}
public int topKey() {
return heap[1].key;
}
public Element topElement() {
return heap[1].element;
}
public int delTop() {
int key = heap[1].key;
delete(key);
return key;
}
public void change(int key, Element element) {
int keyIndex = qp[key];
heap[keyIndex].element = element;
// 恢复堆序列
swim(qp[key]);
sink(qp[key]);
}
public void delete(int key) {
int keyIndex = qp[key];
// 与最后一个元素互换
exch(keyIndex, N--);
// 重构堆序列
swim(keyIndex);
sink(keyIndex);
// 释放数组对应位置废弃的值
heap[N+1] = null;
qp[key] = -1;
}
/**
* 元素上浮, 实现堆序列
*/
private void swim(int k) {
while (k > 1 && (type == Type.Maximum
? less(k/2, k) : !less(k/2, k))) {
exch(k/2, k);
k = k/2;
}
}
/**
* 元素下沉, 实现堆序列
*/
private void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N &&(type == Type.Maximum
? less(j, j + 1) : !less(j, j + 1))) j++;
if (type == Type.Maximum
? !less(k, j) : less(k, j)) break;
exch(k, j);
k = j;
}
}
/**
* 比较大小
*/
private boolean less(int i, int j) {
return heap[i].compareTo(heap[j]) < 0;
}
/**
* 交换元素位置
*/
private void exch(int i, int j) {
// 交换元素位置
Entry<Integer, Element> temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
// 交换存放 key的索引数组的位置
qp[heap[i].key] = i;
qp[heap[j].key] = j;
}
/**
* 存放键值对
*/
public static class Entry<Key, Element extends Comparable<Element>> implements Comparable<Entry<Key, Element>>{
Key key;
Element element;
public Entry(Key key, Element element) {
this.key = key;
this.element = element;
}
@Override
public int compareTo(Entry<Key, Element> other) {
return element.compareTo(other.element);
}
}
}
Prim算法的延时版本
/**
* 最小生成树 Prim 算法的延时实现
*/
public class LazyPrimMST {
private boolean[] marked;// 顶点索引
private Queue<Edge> mst;// 用于存放最小生成树的边
private PriorityQueue<Edge> pq;// 用于存放横切边
public LazyPrimMST(EdgeWeightedGraph G) {
marked = new boolean[G.V()];
mst = new ConcurrentLinkedQueue <>();
pq = new PriorityQueue<Edge>(PriorityQueue.Type.Minimum, G.V());
// 用 0 初始化横切边
visit(G, 0);
// 开始寻找最小生成树
find(G);
}
/**
* 将第 v 个顶点的边加入最小优先队列,
* 这样就可以使用 delMin() 来获取横切边的最小值
* @param G
* @param v
*/
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e: G.adj(v)) {
pq.insert(e);
}
}
/**
* 开始寻找
* @param G
*/
private void find(EdgeWeightedGraph G) {
while(!pq.isEmpty()) {
// 1. 获取最小的横切边
Edge e = pq.delTop();
// 2. 处理获取到的横切边
int v = e.either();
int w = e.other(v);
if (marked[v] && marked[w]) continue;// 跳过失效的边
mst.offer(e);// 将边添加到生成树中
if (!marked[v]) visit(G, v);// 将顶点(v 或 w)添加到队列中
if (!marked[w]) visit(G, w);
}
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
double sumWeight = 0;
for (Edge edge: mst) {
sumWeight += edge.weight();
}
return sumWeight;
}
}
Prim算法的及时版本
/**
* 最小生成树 Prim 算法的及时实现
*/
public class InstantlyPrimMST {
private boolean marked[];
private Edge[] edgeTo;// 距离树最近的边
private double[] distTo;// distTo[w] = edgeTo[w].weight();
private IndexEntryPriorityQueue<Double> pq;// 有效的横切边
public InstantlyPrimMST(EdgeWeightedGraph G) {
marked = new boolean[G.V()];
edgeTo = new Edge[G.V()];
// 初始化边的 distTo 每个点之间的距离为最大值
distTo = new double[G.V()];
for (int i = 0; i < G.V(); i++) {
distTo[i] = Double.MAX_VALUE;
}
pq = new IndexEntryPriorityQueue<>(IndexEntryPriorityQueue.
Type.Minimum, G.V());
find(G);
}
private void find(EdgeWeightedGraph G) {
// 用顶点 0 来初始化 distTo
distTo[0] = 0.0;
// 用顶点 0 和权重 0 来初始化 pq
pq.insert(0, 0.0);
// 遍历
while(!pq.isEmpty()) {
visit(G, pq.delTop());// 将最近的顶点添加到生成树中
}
}
private void visit(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]) {
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)) pq.change(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
}
public Iterable<Edge> edges() {
List<Edge> mst = new ArrayList<>();
for (int v = 1; v < edgeTo.length; v++) {
if (edgeTo[v] == null) continue;
mst.add(edgeTo[v]);
}
return mst;
}
}
调用
public class Main {
public static void main(String[] args) {
// 最小生成树
EdgeWeightedGraph graph = new EdgeWeightedGraph(10);
graph.addEdge(new Edge(0, 1, 0.5));
graph.addEdge(new Edge(0, 2, 0.3));
graph.addEdge(new Edge(1, 3, 0.1));
graph.addEdge(new Edge(3, 0, 0.9));
graph.addEdge(new Edge(3, 6, 0.7));
graph.addEdge(new Edge(6, 7, 0.3));
graph.addEdge(new Edge(7, 8, 0.3));
graph.addEdge(new Edge(7, 3, 0.3));
// 延时 Prim 算法
System.out.println("--------------------LazyPrimMST--------------------");
LazyPrimMST mst = new LazyPrimMST(graph);
for (Edge e: mst.edges()) {
System.out.println(e.toString());
}
// 及时 Prim 算法
System.out.println("--------------------InstantlyPrimMST--------------------");
InstantlyPrimMST inmst = new InstantlyPrimMST(graph);
for (Edge e: inmst.edges()) {
if (e != null) {
System.out.println(e.toString());
}
}
}
}
image.png
