贪心策略最小生成树prim和克利斯卡尔JAVA算法源程序.doc
文本预览下载声明
实验报告9
课程 数据结构与算法 贪心策略 第 页
班级 11计本 学号 105032011130 姓名 风律澈
实验日期：2013年4月27日 报告退发 (订正 、 重做)
一、实验目的
掌握贪心策略的原理和应用。
二、实验环境
1、微型计算机一台
2、WINDOWS操作系统
public class main {
/**
* @param args
*/
public static final int maxvalue=Integer.MAX_VALUE;
public static void main(String[] args) {
// TODO Auto-generated method stub
int weight[][]={
{0,6,1,5,maxvalue,maxvalue},
{6,0,5,maxvalue,3,maxvalue},
{1,5,0,5,6,4},
{5,maxvalue,5,0,maxvalue,2},
{maxvalue,3,6,maxvalue,0,6},
{maxvalue,maxvalue,4,2,6,0},
};
graph a=new graph(weight);
a.showprimtree();
}
}
import java.util.ArrayList;
import java.util.PriorityQueue;
public class graph {
private ArrayListvex vexs;//定义顶点，进入顶点定义初始化
public graph(int weight[][]){
super();
this.vexs=new ArrayListvex();//生成顶点集对象实例
//start和end是在下面程序中使用以构造边的//
vex start;
vex end;
for(int i=0;iweight.length;i++)//对顶点集的每个元素生成点对象实例
this.vexs.add(new vex());
for(int i=0;iweight.length;i++){//对每个元素进行构造初始化
start=this.vexs.get(i);
for(int j=0;jweight.length;j++){
if(weight[i][j]!=Integer.MAX_VALUE){
end=this.vexs.get(j);
new side(start,end,weight[i][j]);
}
}
}
}//至此图的所有成分的信息已经完成，返回main
public ArrayListside prim(){
ArrayListside tree=new ArrayListside();
PriorityQueueside pq=new PriorityQueueside();
vex v = this.vexs.get(0);
v.setcheck(1);
side s;
pq.addAll(v.getsides());
while (true) {
if(pq.isEmpty())break;
s=pq.poll();
if(s.check_intree()==1){
s.un_in();
continue;
}
v=s.add_tree();
tree.add(s);
pq.addAll(v.getsides());
}
return tree;
}
public void showprimtree() {
System.out.println(prim());
}
}
import java.util.ArrayList;
public class vex {
private static int ids=0;
private int id;
private int check;
ArrayListside sides;
public vex(){
super();
id=ids++;
check=0;
side
显示全部