用于最小生成树的Kruskal算法实现

Love The Way You Lie 2022-03-20 07:56 147阅读 0赞

Kruskal算法和Prim算法，作为最古老和最知名的算法，是用于求解一个连通图最小生成树问题的。在下一节我们我们会讲解另一种算法，在这一节里我们来学习一下什么是Kruskal算法。

首先我们来看看什么是生成树，什么是最小生成树？生成树是指在一个连通图中由图中所有顶点和一些边所组成的无环连通子图。在加权无向图中，最小生成树是指权值和最小的生成树。

在上个算法中我们学习了加权无向图该如何表示，由于在这个算法中需要用到边的数组，所以我们在加权无向图的代码实现中添加下面的函数，用于方便的获得无向图中所含有的边的集合。

public Edge\[\] edgeArray()

Edge\[\]edge=new Edge\[edges.size()\];

int i=0;

for(Edgee:edges)

edge\[i++\]=e;

return edge;

下面我们来说说Kruskal算法是如何解决最小生成树问题的。

首先，加权无向图中所有的顶点都作为一个孤立的树，然后对图中的所有边按照权值的大小进行排序，这里我们使用一个基于二叉堆实现的最小优先级队列，使用一个集合来保存我们找到的符合最小生成树的边。我们从这样的优先队列中依次取出每条边(u,v)，判断顶点u和顶点v是否处于同一个树中，如果不属于同一个树，则将这两个顶点连在一起，如果属于同一个树，则从优先队列中选择下一条边继续判断，直到优先队列为空或者我们找到的最小生成树的边数等于图G的顶点数减1。

在上面的算法中，我们需要用到一个判断两个顶点是否处于同一个树的算法，这时我们需要用到一个以前讲过的算法，用于解决连通性问题的UnionFind类，该类使用一个大小为图顶点数的数组来保存各个顶点，而数组中保存的值标志着每个顶点所在的不同集合。该类的具体实现如下：

//动态连通性问题（针对整数对）

package com.chapter1;

import java.util.Scanner;

public class UnionFind \{

private int\[\]id=null;//记录触点所在的分量

private int count=0;//记录分量数

//advancedQuickFind方法添加的变量

private intsize\[\]=null;

public UnionFind(intcount)

this.count=count;

id=newint\[count\];

size=newint\[count\];

for(inti=0;i<count;i++)

id\[i\]=i;

size\[i\]=1;

public int count()

returncount;

public int find(int p)

returnid\[p\];

public booleanconnected(int p, int q)

returnfind(p)==find(q);

public void union(intp, int q)

intpID=find(p);

intqID=find(q);

if(pID==qID)

return;

for(inti=0;i<id.length;i++)

if(id\[i\]==pID)

id\[i\]=qID;

count--;

public intquickfind(int p)

while(id\[p\]!=p)

p=id\[p\];

return p;

public voidquickunion(int p, int q)

intpRoot=quickfind(p);

intqRoot=quickfind(q);

if(pRoot==qRoot)

return;

id\[pRoot\]=qRoot;

count--;

public booleanquickconnected(int p, int q)

returnquickfind(p)==quickfind(q);

public voidadvancedQuickUnion(int p, int q)

intpRoot=quickfind(p);

intqRoot=quickfind(q);

if(pRoot==qRoot)

return;

if(size\[pRoot\]<size\[qRoot\])

id\[pRoot\]=qRoot;

size\[qRoot\]+=size\[pRoot\];

\}else

id\[qRoot\]=pRoot;

size\[pRoot\]+=size\[qRoot\];

public static voidmain(String\[\] args) \{

System.out.println("输入触点个数：");

Scannerin=new Scanner(System.in);

intcount=in.nextInt();

UnionFindsample=new UnionFind(count);

System.out.println("输入整数对数量：");

intpaircount=in.nextInt();

System.out.println("输入整数对：");

for(inti=0;i<paircount;i++)

intp=in.nextInt();

intq=in.nextInt();

for(intj=0;j<count;j++)

System.out.print(sample.id\[j\]+"");

System.out.println();

if(sample.quickconnected(p,q))

continue;

sample.advancedQuickUnion(p,q);

for(intj=0;j<count;j++)

System.out.print(sample.id\[j\]+"");

下面我们看看基于最小堆的优先级队列时如何实现的。

package com.chapter4;

import java.util.Comparator;

import java.util.Iterator;

import java.util.NoSuchElementException;

//基于二叉堆的最小优先级队列

public class MinPriorityQueue<Key> implementsIterable<Key>\{

private Key\[\] pq;

private int N;

privateComparator<Key> comparator;

publicMinPriorityQueue(int capacity)

pq=(Key\[\])newObject\[capacity+1\];

N=0;

publicMinPriorityQueue(int capacity,Comparator<Key> comparator)

this.comparator=comparator;

pq=(Key\[\])newObject\[capacity+1\];

N=0;

publicMinPriorityQueue(Key\[\] keys)

N=keys.length;

pq=(Key\[\])newObject\[N+1\];

for(inti=0;i<N;i++)

pq\[i+1\]=keys\[i\];

for(intk=N/2;k>=1;k--)

sink(k);

public booleanisEmpty()\{return N==0;\}

public intsize()\{return N;\}

private voidresize(int capacity)

assertcapacity>N;

Key\[\]tmp=(Key\[\])new Object\[capacity\];

for(inti=1;i<=N;i++)

tmp\[i\]=pq\[i\];

pq=tmp;

public Key min()//返回优先队列最小值

if(N==0)

thrownew NoSuchElementException("Priority Queue Underflow.");

returnpq\[1\];

public Key deleteMin()//从优先队列中删除最小值

if(isEmpty())

thrownew NoSuchElementException("Priority Queue Underflow.");

exchange(1,N);

Keymin=pq\[N--\];

sink(1);

pq\[N+1\]=null;

if(N>=0&&N==((pq.length-1)/4))

resize(pq.length/2);

assertisMinHeap();

return min;

public void insert(Keyk)//插入

if(N==pq.length-1)

resize(2\*pq.length);

pq\[++N\]=k;

swim(N);

assertisMinHeap();

private void sink(intk)//从上往下的堆有序化实现

int j;

while(2\*k<=N)

j=2\*k;

if(j<N&&greater(j,j+1))j++;

if(!greater(k,j))break;

exchange(k,j);

k=j;

private void swim(intk)//从下往上的堆有序化实现

while(k>1&&greater(k/2,k))

exchange(k/2,k);

k=k/2;

private booleangreater(int i,int j)//比较大小

if(comparator==null)

return((Comparable<Key>)pq\[i\]).compareTo(pq\[j\])>0;

else

returncomparator.compare(pq\[i\], pq\[j\])>0;

private voidexchange(int i,int j)//交换

Keytmp=pq\[i\];

pq\[i\]=pq\[j\];

pq\[j\]=tmp;

public booleanisMinHeap()//检查是否是最小堆

returnisMinHeap(1);

private booleanisMinHeap(int k)

if(k>N)return true;

intleft=2\*k,right=2\*k+1;

if(left<=N&&greater(k,left))return false;

if(right<=N&&greater(k,right))return false;

returnisMinHeap(left)&&isMinHeap(right);

@Override

publicIterator<Key> iterator() \{

// TODOAuto-generated method stub

return newHeapIterator();

private classHeapIterator implements Iterator<Key>

privateMinPriorityQueue<Key> copy;

publicHeapIterator()

if(comparator==null)

copy=newMinPriorityQueue<Key>(size());

else

copy=newMinPriorityQueue<Key>(size(),comparator);

for(inti=1;i<=N;i++)

copy.insert(pq\[i\]);

@Override

publicboolean hasNext() \{

//TODO Auto-generated method stub

return!copy.isEmpty();

@Override

public Keynext() \{

//TODO Auto-generated method stub

if(!hasNext())

thrownew NoSuchElementException("Priority Heap underflow.");

returncopy.deleteMin();

@Override

public voidremove() \{

//TODO Auto-generated method stub

thrownew UnsupportedOperationException();

在实现了优先队列和用于判断连通性的UnionFind类之后我们就可以很容易的来对一个加权连通图求解它的最小生成树了，上面已经给出了具体的思路，下面给出代码实现：

package com.chapter4;

import com.chapter1.UnionFind;

import java.util.Queue;

import java.util.LinkedList;;

//基于kruskal算法的最小生成树实现

public class KruskalMST \{

privateQueue<Edge> mst;

publicKruskalMST(EdgeWeightedGraph G)

mst=newLinkedList<Edge>();

MinPriorityQueue<Edge>mpq=new MinPriorityQueue<Edge>(G.edgeArray());

UnionFinduf=new UnionFind(G.V());

while(!mpq.isEmpty()&&mst.size()<G.V()-1)

Edgee=mpq.deleteMin();

intv=e.either(),w=e.other(v);

if(uf.quickconnected(v,w))

continue;

uf.quickunion(v,w);

mst.add(e);

public StringtoString()

if(mst.isEmpty())

return"无最小生成树";

StringBuildersb=new StringBuilder();

sb.append("最小生成树的边情况为：\\n");

doublecost=0.0;

for(Edgee:mst)

sb.append(e.toString()+"\\n");

cost+=e.weight();

sb.append("总代价为："+cost+"\\n");

returnsb.toString();

public static voidmain(String\[\] args) \{

// TODOAuto-generated method stub

In in=newIn("tinyEWG.txt");

EdgeWeightedGraphgraph=new EdgeWeightedGraph(in);

KruskalMSTsample=new KruskalMST(graph);

System.out.println(sample);

在main函数中，我们对加权连通图tinyEWG.txt进行了测试，可以给出正确的结果，测试结果如下：

最小生成树的边情况为：

0--7\[0.16000\]

2--3\[0.17000\]

1--7\[0.19000\]

0--2\[0.26000\]

5--7\[0.28000\]

4--5\[0.35000\]

6--2\[0.40000\]

总代价为：1.81

正如while(!mpq.isEmpty()&&mst.size()<G.V()-1)所示，该算法在找到V-1条边之后就会终止，实际的成本应该和E+E0\*lgE成正比，而E0是权重小于最小生成树中权重最大的边的所有边的总数。

用于最小生成树的Kruskal算法实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关最小生成树之kruskal算法

相关求最小生成树Kruskal算法

相关最小生成树的Kruskal算法

相关最小生成树Kruskal算法实现C++实现

相关笔记：最小生成树——Kruskal算法

相关【算法】图的最小生成树(Kruskal算法)

相关最小生成树Kruskal算法实现C++实现

相关用于最小生成树的Prim算法实现

相关用于最小生成树的Kruskal算法实现

相关最小生成树（kruskal）