Kruskal 算法的Java实现

      最近学习算法分析与设计，说真的还挺好的，虽然理论啊上不是很清楚，但是我很欣喜里面的思想。俗话说思想有多远就能走多远。呵呵，努力搞好吧！加油！废话不多说还是把代码贴上来吧：

package com.sfsj.chap3;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入一个带权的连通无向图 生成该图的最小生成树 该类实现kruskal算法 该算法以边为主 适用于边多点少的图形中
 *
 * @author lxy
 */
public class Kruskal {
 /**
  * 代表字符的数字 A-0, B-1, C-2, D-3 ，E-4
  */
 // 当两个顶点没有连线的时候将其权值设为MOUSTMAX
 private static final int MOUSTMAX = 1000;
 // 保存点集的第一个集合
 private static List<String> START = new ArrayList<String>();
 // 保存点集的第二个集合
 private static List<String> END = new ArrayList<String>();

 /**
  * 程序的入口
  *
  * @param args
  */
 public static void main(String[] args) {
  // 声明一个二维数组保存边的权值
  int[][] array = new int[5][5];
  // 给二维数组全部赋值
  for (int i = 0; i < array.length; i++) {
   for (int j = 0; j < array.length; j++) {
    array[i][j] = MOUSTMAX;
   }
  }
  // 输入边的权值
  array[0][2] = 200;// AC权值为200
  array[0][3] = 80;// AD权值为80
  array[0][4] = 50;// AE权值为50
  array[1][2] = 70;// BC权值为70
  array[1][3] = 75;// BD权值为75
  array[1][4] = 300;// BE权值为300
  array[2][3] = 60;// CD权值为60
  array[3][4] = 90;// DE权值为90
  // 边的条数
  int count = 0;

  for (int i = 0; i < array.length; i++) {
   for (int j = 0; j < array.length; j++) {
    if (array[i][j] != MOUSTMAX) {
     count++;
    }
   }
  }
  // 调用排序
  while (count > 0) {
   Kruskal.sort(array);
   count--;
  }
 }

 /**
  * @param array
  *            带权值的二维数组
  */
 public static void sort(int[][] array) {
  int min = array[0][0];
  // 找到当前二维数组中最小的值
  for (int i = 0; i < array.length; i++) {
   for (int j = 0; j < array.length; j++) {
    if (array[i][j] <= min) {
     min = array[i][j];
    }
   }
  }

  // 定义两个变量存储相应坐标，二维数组中有array[0][0]所以如下定义
  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 (array[i][j] == min) {
     array[i][j] = MOUSTMAX;
     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 + " ");
  }
 }

 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) && 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();
    }
    if (START.contains(charx) && END.contains(chary)) {
     last.add(charx + chary);
     for (String char1 : START) {
      if (!END.contains(char1)) {
       END.add(char1);
      }
     }
    }
    // 如果两点都不在某点集中，那么添加另外一个集合保存新的点集
    if (!END.contains(charx) && !END.contains(chary)) {
     last.add(charx + chary);
     if (!START.contains(charx) && !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 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;
 }

}

 

评论

5 楼 hyneng 2010-10-13  

算法学习有什么资源或书推荐吗

4 楼 潇潇暮雨 2009-09-29  

yuanji200603 写道

这个循环的条件count>0感觉也有问题，不是边取完了 就结束啊，是顶点 取完 结束

Kruskal算法是针对于点少边多的情况的，我个人认为Kruskal是针对于边的，而不是针对于顶点，prm算法是针对于顶点！

3 楼 潇潇暮雨 2009-09-29  

yuanji200603 写道

问一下，如果只有5个点的话，上面的两个点集是可以的，但是如果有很多点集呢。

恩这个问题是还没有解决的，我也在看书在查找相关资料

2 楼 yuanji200603 2009-09-25  

这个循环的条件count>0感觉也有问题，不是边取完了 就结束啊，是顶点 取完 结束

1 楼 yuanji200603 2009-09-25  

问一下，如果只有5个点的话，上面的两个点集是可以的，但是如果有很多点集呢。