易截截图软件、单文件、免安装、纯绿色、仅160KB

最小生成树 Prim算法 java代码实现

 /*
*日期:2010-04-18 11:37
*开发者:heroyan
*联系方式:zndxysf@126.com
*功能:无向图最小生成树Prim算法实现案例
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class SpanningTree{
private static int MAX = 100;
private double cost[][] = new double[MAX][MAX];
private ArrayList<Edge> edge = new ArrayList<Edge>();
private int[] near = new int[MAX];
private static double INFINITY = 99999999.99;//定义无穷大
private double mincost = 0.0;//最小成本
private int n;//结点个数

public SpanningTree(){}

public static void main(String args[]){
SpanningTree sp = new SpanningTree();
sp.init();
sp.prim();
sp.print();
}
//初始化
public void init(){
Scanner scan = new Scanner(System.in);
int p,q,w;

System.out.println("spanning tree begin!Input the node number:");
n = scan.nextInt();
//二维数组的填充要注意
for(int i = 0; i < MAX; ++i){
Arrays.fill(cost[i],INFINITY);
}
System.out.println("Input the graph(-1,-1,-1 to exit)");

while(true){
p = scan.nextInt();
q = scan.nextInt();
w = scan.nextInt();
if(p < 0 || q < 0 || w < 0){
break;
}
cost[p][q] = w;
cost[q][p] = w;
}

Edge tmp = getMinCostEdge();
edge.add(tmp);
p = tmp.start;
q = tmp.end;
mincost = cost[p][q];

for(int i = 1; i <= n; ++i){
if(cost[i][p] < cost[i][q]){
near[i] = p;
}else{
near[i] = q;
}
}
near[p] = near[q] = 0;
}
//寻找最小成本的边
public Edge getMinCostEdge(){
Edge tmp = new Edge();
double min = INFINITY;

for(int i = 1; i < n; ++i){
for(int j = i+1; j <= n; ++j){
if(cost[i][j] < min){
min = cost[i][j];
tmp.start = i;
tmp.end = j;
}
}
}
//System.out.println(min);
return tmp;
}
//prim算法主体
public void prim(){
//找剩下的n-2条边
for(int i = 2; i < n; ++i){
double min = INFINITY;
Edge


相关文档:

Java Builder 初体验

原创】Java Builder 初体验
2006-10-19 11:43 junziyang
【原创】Java Builder 初体验
MATLAB的最新版本2006b中新添了一个产品-MATLAB Builder for Java。其实本来Matlab就有Java外部程序接口,不过原来的接口只能在.m文件中调用Java,而无法在Java程序中调用Matlab。新的Java Builder为我们在Java程序中调用Matlab丰富 ......

Java中toArray的用法探究(java数组与list转换)


一.             Incident
import java.util.ArrayList;  
import java.util.List;  
public class Test {  
    public static void main(String[] args) {  
     ......

Serializable java序列化

Bean Serializable Interface 的接口让BEAN可以串行化,将其变成一个可保存为以后使用的二进制流。当一个BEAN被系列化到磁盘上或者其他任何地方,其状态被保存起来,其中的属性值也不会改变。在BEAN的规范中,JSP并没有要求BEAN实现Serializable接口。但是,如果您希望自己控制您所创建的组件的serialization进程,或者您想 ......

Java学习 从入门到精通


Java Learning Path (一)、工具篇
一、 JDK (Java Development Kit)
JDK是整个Java的核心,包括了Java运行环境(Java Runtime Envirnment),一堆Java工具和Java基础的类库(rt.jar)。不论什么Java应用服务器实质都是内置了某个版本的JDK。因此掌握JDK是学好Java的第一步。最主流的JDK是Sun公司发布的JDK,除了Sun之外 ......

★★★★★这几天的java学习

      这几天的学习 让我感到发懵,老师讲的很多,自己就根本无法去思考,只能一个劲的往里听,自己代码也不怎么会,老师讲过的能有个印象, 不过今天还好,讲到了Java基础加强,稍微感觉好点,并不是很难理解了,今天就开始今天课程的复习了,要想进步,只有自己艰苦努力啦!
    确 ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号