Java實現(xiàn)Kruskal算法的示例代碼

第Java實現(xiàn)Kruskal算法的示例代碼目錄介紹一、構(gòu)建后的圖二、代碼三、測試

介紹

構(gòu)造最小生成樹還有一種算法，即Kruskal算法：設(shè)圖G=（V，E）是無向連通帶權(quán)圖，V={1,2，...n};設(shè)最小生成樹T=(V，TE)，該樹的初始狀態(tài)只有n個節(jié)點而無邊的非連通圖T=(V,{}),Kruskal算法將這n個節(jié)點看成n個孤立的連通分支。它首先將所有邊都按權(quán)值從小到大排序，然后值要在T中選的邊數(shù)不到n-1,就做這樣貪心選擇：在邊集E中選擇權(quán)值最小的邊(i,j),如果將邊(i,j)加入集合TE中不產(chǎn)生回路，則將邊(i,j)加入邊集TE中，即用邊(i，j)將這兩個分支合并成一個連通分支；否則繼續(xù)選擇下一條最短邊。把邊(i,j)從集合E中刪去，繼續(xù)上面的貪心選擇，直到T中的所有節(jié)點都在同一個連通分支上為止。此時，選取的n-1條邊恰好構(gòu)成圖G的一棵最小生成樹T。

Kruskal算法用一種非常聰明的方法，就是運用集合避圈；如果所選擇加入邊的起點和終點都在T集合中，就可以斷定會形成回路，變的兩個節(jié)點不能屬于同一個集合。

算法步驟

1初始化。將所有邊都按權(quán)值從小到大排序，將每個節(jié)點集合號都初始化為自身編號。

2按排序后的順序選擇權(quán)值最小的邊（u,v）。

3如果節(jié)點u和v屬于兩個不同的連通分支，則將邊(u,v)加入邊集TE中，并將兩個連通分支合并。

4如果選取的邊數(shù)小于n-1,則轉(zhuǎn)向步驟2，否則算法結(jié)束。

一、構(gòu)建后的圖

二、代碼

packagegraph.kruskal;

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.List;

importjava.util.Scanner;

publicclassKruskal{

staticfinalintN=100;

staticintfa[]=newint[N];

staticintn;

staticintm;

staticEdgee[]=newEdge[N*N];

staticListEdgeedgeList=newArrayList();

static{

for(inti=0;ie.length;i++){

e[i]=newEdge();

//初始化集合號為自身

staticvoidInit(intn){

for(inti=1;ii++)

fa[i]=i;

//合并

staticintMerge(inta,intb){

intp=fa[a];

intq=fa[b];

if(p==q)return0;

for(inti=1;ii++){//檢查所有結(jié)點，把集合號是q的改為p

if(fa[i]==q)

fa[i]=p;//a的集合號賦值給b集合號

return1;

//求最小生成樹

staticintKruskal(intn){

intans=0;

Collections.sort(edgeList);

for(inti=0;ii++)

if(Merge(edgeList.get(i).u,edgeList.get(i).v)==1){

ans+=edgeList.get(i).w;

n--;

if(n==1)//n-1次合并算法結(jié)束

returnans;

return0;

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

n=scanner.nextInt();

m=scanner.nextInt();

Init(n);

for(inti=1;ii++){

e[i].u=scanner.nextInt();

e[i].v=scanner.nextInt();

e[i].w=scanner.nextInt();

edgeList.add(e[i]);

System.out.println("最小的花費是："+Kruskal(n));

classEdgeimplementsComparable{

intu;

intw;

intv;

@Override

publicintcompareTo(Objecto){

if(this.w((Edge)o).w){

re