Kruskal算法求最小生成树(java).doc

Kruskal算法求最小生成树（JAVA）代码：package homework;import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; class Edge public int start;/始边 public int end;/终边 public double cost;/权重 public class MinSpanningTree_Kruskal private static int MAX = 100; private ArrayList edge = new ArrayList();/整个图的边 private ArrayList target = new ArrayList();/目标边，最小生成树 private int parent = new intMAX;/标志所在的集合 private static double INFINITY = 99999999.99;/定义无穷大 private double mincost = 0.0;/最小成本 private int n;/结点个数 public MinSpanningTree_Kruskal() public static void main(String args) MinSpanningTree_Kruskal sp = new MinSpanningTree_Kruskal(); sp.init(); sp.kruskal(); sp.print(); /初始化 public void init() Scanner scan = new Scanner(System.in); int p,q; double w; System.out.println(请输入结点个数：); n = scan.nextInt(); System.out.println(请输入各条边及权值（每次输入一组数据按回车确认， + 最后输入-1 -1 -1 结束输入过程）); 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) parenti = i; /集合合并 public void union(int j, int k) for(int i = 1; i = n; +i) if(parenti = j) parenti = k; /prim算法主体 public void kruskal() /找剩下的n-2条边 int i = 0; while(i 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 = parenttmp.start; int kk = parenttmp.end; /去掉环 if(jj != kk) +i; target.add(tmp); mincost += tmp.cost; union(jj,kk); edge.remove(tmp); if(i != n-1) System.out.println(没有最小生成树); System.exit(0); /打印结果 public void print() double sum=0; System.out.println(最小生成树：); for(int i = 0; i target.size(); +i) Edge e = target.get(i); System.out.println(第 + (i+1) + 条边: + e