Prim算法和Kruskal算法 Java实现
Prim算法
public class Prim {
public static int inf=65535;
public static int minval=0;
public static void prim(int [][]map,int n) {
int min,i,j,k;
int visit[]=new int[n];//0表示未选择 ；1表示已选择
int lowcost[]=new int[n];//表示顶点i到已选择的顶点集中的最短边的权值 若i在顶点集中，则为inf
//首先选择点0
lowcost[0]=inf;
visit[0]=1;
for(i=1;i<n;i++)
{
lowcost[i]=map[0][i];
visit[i]=0;
}
for(i=1;i<n;i++)//循环n-1次，选择剩下的n-1个点
{
min=inf;
k=0;
//寻找连接已选择的顶点集到未选择的顶点集的最小权值边
for(j=1;j<n;j++)
{
if(visit[j]==0&&lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
}
//选择顶点k，记录总权值
minval+=min;
lowcost[k]=inf;
visit[k]=1;
//更新lowcost
for(j=1;j<n;j++)
{
if(visit[j]==0&&map[k][j]<lowcost[j])
{
lowcost[j]=map[k][j];
}
}
}
}
public static void main(String[] args) {
int map[][]= {{0,10,inf,inf,inf,11,inf,inf,inf},
{10,0,18,inf,inf,inf,16,inf,12},
{inf,inf,0,22,inf,inf,inf,inf,8},
{inf,inf,22,0,20,inf,inf,16,21},
{inf,inf,inf,20,0,26,inf,7,inf},
{11,inf,inf,inf,26,0,17,inf,inf},
{inf,16,inf,inf,inf,17,0,19,inf},
{inf,inf,inf,16,7,inf,19,0,inf},
{inf,12,8,21,inf,inf,inf,inf,0},
};
prim(map,map.length);
System.out.print("最小生成树的权值为："+minval);
}
}
Kruskal算法
import java.util.*;
class Edge{
int begin;
int end;
int weight;
public int getWeight()
{
return weight;
}
}
public class Kruskal {
public static int inf=65535;
public static int minval=0;
public static void kruskal(int map[][]) {
int i,j,m,n;
int parent[]=new int[map.length];
//读入所有边，并按权值从小到大排序
List<Edge>edges=new ArrayList<Edge>();//定义边集数组
for(i=0;i<map.length;i++)
{
for(j=0;j<map.length;j++)
{
if(map[i][j]!=inf&&map[i][j]!=0)
{
Edge edge=new Edge();
edge.begin=i;
edge.end=j;
edge.weight=map[i][j];
edges.add(edge);
}
}
}
//按权由大到小排序
edges.sort(Comparator.comparingInt(Edge::getWeight));
//初始化并查集
for(i=0;i<map.length;i++)
{
parent[i]=0;
}
//循环所有边
for(i=0;i<edges.size();i++)
{
n=find(parent,edges.get(i).begin);
m=find(parent,edges.get(i).end);
if(n!=m)//n与m不相等，说明此边没有与现有的生成树形成环路
{
//将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中
parent[n]=m;
minval+=edges.get(i).weight;
}
}
}
//查找连线顶点的尾部下标
public static int find(int parent[],int f)
{
while(parent[f]>0)
{
f=parent[f];
}
return f;
}
public static void main(String[] args) {
int map[][]= {{0,10,inf,inf,inf,11,inf,inf,inf},
{10,0,18,inf,inf,inf,16,inf,12},
{inf,inf,0,22,inf,inf,inf,inf,8},
{inf,inf,22,0,20,inf,inf,16,21},
{inf,inf,inf,20,0,26,inf,7,inf},
{11,inf,inf,inf,26,0,17,inf,inf},
{inf,16,inf,inf,inf,17,0,19,inf},
{inf,inf,inf,16,7,inf,19,0,inf},
{inf,12,8,21,inf,inf,inf,inf,0},
};
kruskal(map);
System.out.print("最小生成树的权值为："+minval);
}
}