kruskal算法java_算法java實作–貪心算法–最小生成樹問題–Kruskal算法 | 學步園...

最小生成樹問題(Kruskal

具體問題描述以及C/C++實作參見網址

http://blog.csdn.net/liufeng_king/article/details/8738161

import java.util.Collections;

import java.util.LinkedList;

import java.util.List;

public class KrusKal {

public static class FastUnionFind {

public int[] u;//數組用來儲存頂點所屬的集合，用數字表示

public FastUnionFind(int n){

u=new int[n+1];

for(int i=1;i<=n;i++){//初始化，起初每個頂點所屬的集合名稱即相應的頂點數字

u[i]=i;

}

}

public int find(int x){//找到頂點所屬的集合

return u[x];

}

public void union(int x,int y){//将第二個點歸入第一個點的集合(集合名字用數字表示)

u[y]=u[x];

}

}

public static class EdgeNode implements Comparable{

float weight;//邊的權重

int u;//邊的左頂點

int v;//邊的右頂點

public EdgeNode(int uu,int vv,float ww){

u=uu;

v=vv;

weight=ww;

}

@Override

public int compareTo(Object x) {//升序排序(從小到大)，LinkedList的first就指向長度最短的邊

float xw=((EdgeNode)x).weight;

if(weight

if(xw==weight) return 0;

return 1;

}

}

public static boolean kruskal(int n,LinkedList E,EdgeNode[] t){

FastUnionFind U=new FastUnionFind(n);

int k=0;

while(k

EdgeNode x=E.peek();

int a=U.find(x.u);//邊的左頂點所屬的集合

int b=U.find(x.v);//邊的右頂點所屬的集合

if(a!=b){

t[k++]=x;

U.union(a, b);

}

E.pop();

}

for(int i=0;i

System.out.println("左頂點："+t[i].u+"； 右頂點："+t[i].v+"; 長度："+t[i].weight);

}

return (k==n-1);

}

public static void main(String[] args) {

int n=6;

EdgeNode e1=new EdgeNode(1,2,6);

EdgeNode e2=new EdgeNode(1,3,1);

EdgeNode e3=new EdgeNode(1,4,5);

EdgeNode e4=new EdgeNode(2,3,5);

EdgeNode e5=new EdgeNode(3,4,5);

EdgeNode e6=new EdgeNode(2,5,3);

EdgeNode e7=new EdgeNode(3,5,6);

EdgeNode e8=new EdgeNode(5,6,6);

EdgeNode e9=new EdgeNode(3,6,4);

EdgeNode e10=new EdgeNode(4,6,2);

LinkedList E=new LinkedList();

E.add(e10);

E.add(e9);

E.add(e8);

E.add(e7);

E.add(e6);

E.add(e5);

E.add(e4);

E.add(e3);

E.add(e2);

E.add(e1);

Collections.sort(E);

EdgeNode[] t=new EdgeNode[n];

kruskal(n,E,t);

}

}