1.算法詳解
Kruskal算法類似于Prim算法,不過Prim算法以點為機關,Kruskal主要考慮邊,Kruskal算法的思想是将邊排序,之後根據依次出列,如果邊上的兩點不在一棵樹上,我們就可以将這兩棵樹合并成一棵樹,算法思路比Prim算法更加清晰。
2. java源代碼
import java.util.Arrays;
import java.util.*;
public class KruskalMy {
static class Edge implements Comparable<Edge>
{
private int i,j,w;
Edge(int i,int j,int w)
{
this.i=i;
this.j=j;
this.w=w;
}
@Override
public int compareTo(Edge edge) {
if(this.w==edge.w) return 0;
else if(this.w<edge.w) return -1;
else return 1;
}
}
public static void main(String [] args){
int [] V={1,2,3,4,5,6};
Edge [] E=new Edge[10];
E[0]=new Edge(1,2,6);
E[1]=new Edge(1,3,1);
E[2]=new Edge(1,4,5);
E[3]=new Edge(2,3,5);
E[4]=new Edge(2,5,3);
E[5]=new Edge(3,4,5);
E[6]=new Edge(3,5,6);
E[7]=new Edge(3,6,4);
E[8]=new Edge(4,6,2);
E[9]=new Edge(5,6,6);
kruskal(V, E);
}
public static void kruskal(int [] V,Edge [] E)
{
Arrays.sort(E);
int m=V.length;
int n=E.length;
//每個set表示一棵樹,list表示森林
ArrayList<HashSet<Integer>> list=new ArrayList<HashSet<Integer>>();
ArrayList<Edge> edges=new ArrayList<Edge>();
//初始化每個點構成一棵樹
for(int i=0;i<m;i++)
{
HashSet<Integer> set= new HashSet<Integer>();
set.add(V[i]);
list.add(set);
}
//每個邊依次出列
for(int i=0;i<n;i++)
{
Edge edge=E[i];
int a=edge.i;
int b=edge.j;
int counta=-1;
int countb=-1;
//首先要找到邊上兩點所在的樹
for(int j=0;j<list.size();j++){
HashSet<Integer> set=list.get(j);
if(set.contains(a))
{
counta=j;
}
if(set.contains(b))
{
countb=j;
}
}
//沒找到點
if(counta==-1||countb==-1)
{
return;
}
else
{
//兩點在不同的樹
if(counta!=countb)
{
HashSet<Integer> set1=list.get(counta);
HashSet<Integer> set2=list.get(countb);
set1.addAll(set2);
//删除集合的時候要注意。連續删除兩個集合
if(counta<countb){
list.remove(counta);
list.remove(countb-1);
}
else
{
list.remove(countb);
list.remove(counta-1);
}
list.add(set1);
edges.add(edge);
System.out.println("将邊"+edge.i+"--->"+edge.j+"加入,其權值為"+edge.w);
}
else
{
System.out.println("不能加入"+edge.i+"--->"+edge.j+"兩點在同一個樹中");
}
}
}
}
}
3.運作結果
将邊1--->3加入,其權值為1
将邊4--->6加入,其權值為2
将邊2--->5加入,其權值為3
将邊3--->6加入,其權值為4
不能加入1--->4兩點在同一個樹中
将邊2--->3加入,其權值為5
不能加入3--->4兩點在同一個樹中
不能加入1--->2兩點在同一個樹中
不能加入3--->5兩點在同一個樹中
不能加入5--->6兩點在同一個樹中