使用并查集UnionFind和优先队列PriorityQueue实现Kruskal算法

拿到题目，先看看UnionFind 和 PriorityQueue 怎么实现吧，谁让上课没好好听呢。

Kruskal算法是通过按照权值递增的顺序依次选择图中的边，当边不处于同一连通分量时加入生成树，否则舍去此边选择下一条代价最小的边，直到所有顶点都在同一连通分量上。

1.UnionFind并查集

并查集适用于动态连通性问题，比如说最小生成树时判定两节点是否在同一连通分量中等等。java实现如下：

UnionFind.java

public class UnionFind { private int [] id; //每个节点组号 private int [] sz; //每个组的大小 private int count ; //联通分量数目 //初始化 public  UnionFind(int N){ count = N; id = new int[N]; sz = new int[N]; for(int i=0;i<N;i++){ id[i] = i; //初始情况下每个节点的组号就是该节点的序号 sz[i] = 1; //初始时每个组大小都为1 } } //返回联通分量数目 public int count(){ return count; } //检查是否联通，如果是，返回true public boolean connected(int p,int q){ return find(q)==find(p); } //查找组号,压缩路径，使得树更加扁平化，提高了find的效率 public int find(int p){ while(p != id[p]){ //找到它的根节点 //将p节点的父节点设置为它的爷爷节点 id[p] = id[id[p]]; p = id[p]; } return p; } //组合Weighted Quick-Union public void union(int p,int q){ int pID = find(p); int qID = find(q); //如果在同一组直接返回 if(pID==qID) return; //不是就组合,将小树作为大树的子树 else{ if(sz[pID]<sz[qID]){ id[pID] = qID; sz[qID] += sz[pID]; } else{ id[qID] = pID; sz[pID] += sz[qID]; } count -- ;    //联通分量数目减少1 } } }

2.优先队列

用二叉堆实现的优先队列在进行大量数据的插入元素和删除最大、最小元素时效率更高。

PriorityQueue.java

public class PriorityQueue { public  Segment [] pq = new Segment[40]; //pq 为线段类的一个对象数组 private int N = 0; //队列元素个数 public PriorityQueue(int maxN){ //初始化队列 for(int i= 0; i<maxN+1; i++){ pq[i] = new Segment() ; } } public boolean isEmpty(){ return N==0 ; } public int size(){ return N; } public void insert(int v,int i,int j){ //插入队列元素，并按递减排序 pq[++N].weight = v; pq[N].x = i ; pq[N].y = j ; swim(N); //上浮操作 } public int delMin(){ //由于要为最小生成树服务，这里删除的是最小值 int min = pq[1].weight; exch(1, N--); pq[N+1].weight = 9999; //防止末尾元素为空，随便指定一个较大值 sink(1); return min; } //小的游上去 private  void swim(int k){ while(k > 1 && pq[k/2].weight > pq[k].weight){ exch(k/2,k); k = k/2; } } //大的沉下去 private void sink(int k){ while(2*k <= N){ int j = 2*k; if(j<N && pq[j].weight > pq[j+1].weight) j++; if(pq[k].weight < pq[j].weight) break; exch(k, j); k = j ; } } private void exch(int i,int j){ //线段对象交换，开始时我只交换线段的权重，后来修正 Segment temp = pq[i] ; pq[i] = pq[j] ; pq[j] = temp; } }

3.由于Kruskal算法的操作是以线段权重大小为顺序，我们要操作的对象是线段，所以需要构造一个简单的线段类：

Segment.java

package com.zsx; public class Segment { public int weight; //线段的权重 public int x; //线段的两个顶点 public int y; }

4.总函数：

import java.util.Scanner; public class Kruskal { public static void main(String []args){ int N,v,i,j,sum ; System.out.println("请输入节点数："); Scanner in = new Scanner(System.in); N = in.nextInt(); //节点数 UnionFind uf = new UnionFind(N); //创建并查集对象 PriorityQueue weight = new PriorityQueue(N*N); //创建优先队列对象 System.out.println("请输入节点编号及他们之间路径的权重,输入-1结束："); while((i = in.nextInt())!= -1){ //当输入-1时停止输入 int x=0,y=0; j = in.nextInt(); v = in.nextInt(); weight.insert(v,i,j); //优先队列中插入节点 } System.out.println("Kruskal算法构造的最小生成树成功："); for(i=0,sum=0;i< N -1 ;){ //最小生成树中，N个节点最多有N-1条边 int p = weight.pq[1].x; int q = weight.pq[1].y; if(!uf.connected(p,q )){ //按照边的权重从小到大开始选择，当线段的2个节点不在一个连通分量中时选择 System.out.println(weight.pq[1].weight+ " "+p +" "+q ); sum += weight.pq[1].weight; uf.union(p, q); //标记为一个同分量 i++; } weight.delMin(); } System.out.println("权重和："+sum); } }