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

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

/*
*日期:2010-04-18 20:02
*开发者:heroyan
*联系方式:zndxysf@126.com
*功能:无向图最小生成树Kruskal算法实现案例
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Kruskal{
private static int MAX = 100;
private ArrayList<Edge> edge = new ArrayList<Edge>();//整个图的边
private ArrayList<Edge> target = new ArrayList<Edge>();//目标边,最小生成树
private int[] parent = new int[MAX];//标志所在的集合
private static double INFINITY = 99999999.99;//定义无穷大
private double mincost = 0.0;//最小成本
private int n;//结点个数

public Kruskal(){}

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

System.out.println("spanning tree begin!Input the node number:");
n = scan.nextInt();
System.out.println("Input the graph(-1,-1,-1 to exit)");

while(true){
p = scan.nextInt();
q = scan.nextInt();
w = scan.nextDouble();
if(p < 0 || q < 0 || w < 0){
break;
}
Edge e = new Edge();
e.start = p;
e.end = q;
e.cost = w;
edge.add(e);
}

mincost = 0.0;

for(int i = 1; i <= n; ++i){
parent[i] = i;
}
}
//集合合并
public void union(int j, int k){
for(int i = 1; i <= n; ++i){
if(parent[i] == j){
parent[i] = k;
}
}
}
//prim算法主体
public void kruskal(){
//找剩下的n-2条边
int i = 0;
while(i < n-1 && edge.size() > 0){
//每次取一最小边,并删除
double min = INFINITY;
int tag = 0;
Edge tmp = null;
for(int j = 0; j < edge.size(); ++j){
Edge tt = edge.get(j);
if(tt.cost < min){
min = tt.cost;
tmp = tt;
}
}
int jj = parent[tmp.start];
int kk = parent[tmp.end];
//去掉环
if(jj != kk){
++i;
target.add(tmp);
m


相关文档:

Matlab Builder for java problems

from:http://topic.csdn.net/u/20080123/10/28c8cf34-5eb1-40e6-a117-7abe9cd92291.html
1.没有安装matlab2007之前,程序报错:
Exception in thread "main" java.lang.UnsatisfiedLinkError: C:\WINDOWS\system32\nativemcl77.dll
我查找资料发现,如果不安装matlab,则必须要安装MATLAB Component Run-time(MCR),
2. ......

第1章 Java基础

第1章
 
Java基础
 
1.1            Java的历史和基本原理
1.2            Java字节码
1.3            Java术语
1.4 &nbs ......

JAVA面试题及答案(基础题122道)

JAVA相关基础知识
1、面向对象的特征有哪些方面 
1.抽象:
抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节。抽象包括两个方面,一是过程抽象,二是数据抽象。
2.继承:
继承是一种联结类的层 ......

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小知识

(1)Java中的主方法public static void main(String args[])为什么要用static来修饰
因为java是完全面向对象语言,这个主函数其实是一个类的方法,这个方法在类没有生成对象的时候就必须被JVM调用,所以它必须是静态的成员函数.
 (2)java语言中的public static void main(String[] args) 作用是什么.所做的事情又是什 ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号