Kruskal贪心算法实现

1、package com.jungoo.chapter8;import java.util.ArrayList;import java.util.List;/* * 输入一个带权的连通无向图 生成该图的最小生成树 该类实现Kruskal算法 该算法以边为主 适用于边多点少的图形中 * * author administrator */public class Kruskal /* * 代表字符的数字 A-0, B-1, C-2, D-3 ，E-4 */ 当两个顶点没有连线的时候将其权值设为MOUSTMAXprivate static final int MOUSTMAX = 1000;/ 保存点

2、集的第一个集合private static List<String> START = new ArrayList<String>();/ 保存点集的第二个集合private static List<String> END = new ArrayList<String>();/* * param array * 带权值的二维数组 */public static void sort(int array) int min = array00;/ 找到当前二维数组中最小的值for (int i = 0; i < array.length; i+)

3、for (int j = 0; j < array.length; j+) if (arrayij <= min) min = arrayij;/ 定义两个变量存储相应坐标，二维数组中有array00所以如下定义int varx = Integer.MAX_VALUE;int vary = Integer.MAX_VALUE;/ 将最小处的值改变for (int i = 0; i < array.length; i+) for (int j = 0; j < array.length; j+) if (arrayij = min) arrayij = MOUSTMAX;

4、varx = i;vary = j;break;/ 将数字转化成字符String charx = Kruskal.tochar(varx);String chary = Kruskal.tochar(vary);/ 判断是否有环路List<String> laststring = Kruskal.dest(charx, chary);for (String i : laststring) System.out.print(i + " ");/* * 判断是否构成回路 * param charx * X坐标 * param chary * Y坐标 * return

5、 List * String */public static List<String> dest(String charx, String chary) List<String> last = new ArrayList<String>();/ 初始点集为空时if (END.size() = 0) last.add(charx + chary);END.add(charx);END.add(chary); else / 边的坐标并不全在两个点集中的任何一个点集中,如果在任何一个点集就会构成回路if (!(END.contains(charx) &&a

6、mp; END.contains(chary) | START.contains(charx)&& START.contains(chary) / 如果 某点在一个点集中，另一个点在另一个点集中if (END.contains(charx) && START.contains(chary) last.add(charx + chary);/ 构成新的点集for (String char1 : START) if (!END.contains(char1) END.add(char1);START.clear();else if (START.contains(c

7、harx) && END.contains(chary) last.add(charx + chary);for (String char1 : START) if (!END.contains(char1) END.add(char1);/ 如果两点都不在某点集中,那么添加另外一个集合保存新的点集,把这个新的节点保存才START链表中else if (!END.contains(charx) && !END.contains(chary) last.add(charx + chary);if (!START.contains(charx) &&

8、 !START.contains(chary) START.add(charx);START.add(chary);if (START.contains(charx) && !START.contains(chary) START.add(chary);if (!START.contains(charx) && START.contains(chary) START.add(charx);return last;/* * * param var * 代表字符的数字 * return 返回该字符 */public static String tochar(int

9、var) String char1 = ""switch (var) case 0:char1 = "A"break;case 1:char1 = "B"break;case 2:char1 = "C"break;case 3:char1 = "D"break;case 4:char1 = "E"break;return char1;/* * 程序的入口 * * param args */public static void main(String args) / 声明一个二

10、维数组保存边的权值int array = new int55;/ 给二维数组全部赋值for (int i = 0; i < array.length; i+) for (int j = 0; j < array.length; j+) arrayij = MOUSTMAX;/ 输入边的权值array02 = 200;/ AC权值为200array03 = 80;/ AD权值为80array04 = 50;/ AE权值为50array12 = 70;/ BC权值为70array13 = 75;/ BD权值为75array14 = 300;/ BE权值为300array23 = 60;/ CD权值为60array34 = 90;/ DE权值为90/ 边的条数int count = 0;for (int i = 0; i < array.length; i+) for (int j = 0; j < array.length; j+) if(j=array.le