getlittletree.java

破圈法

import java.io.*;

public class GetLittleTree{
        public int dim = 0; //记录图中结点数
        public int[] tem; //用来暂时缓存图中的数据
        public int[][] edge; //使用邻接矩阵表示图
        public int[][] tree; //用来存放最小生成数的邻接矩阵
        public int[] count; //用来记录取去结点
        public int cop = 1 ;//结点计数器
        StreamTokenizer st;
        FileOutputStream fw;
  public GetLittleTree()throws IOException ,FileNotFoundException{
    Reader r = new BufferedReader(new InputStreamReader(new FileInputStream("in.txt")));
    st = new StreamTokenizer(r);
    fw = new FileOutputStream("out.txt");
    st.nextToken();
    st.pushBack();
    st.nextToken();
    dim = (int) st.nval; //获取图中的结点数
    count = new int[dim];
    count[0] = 1; //对于边割法可以任意选取初始点，不仿取第一个结点作为开始结点
    tem = new int[dim*dim];
    edge = new int[dim][dim];
    tree = new int[dim][dim];
	int acc = 0;
	int k = 0;
    while ((st.nextToken()) != st.TT_EOF) {
      st.pushBack();
      st.nextToken();
      tem[acc++] = (int) st.nval;
    }
    /*
     *将缓存在数组中的数据转移到表示图的二维数据结构中
     */
     for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
          edge[i][j] = tem[k++];
        }
     }//for
  }
/*
 *对于边割法可以任意选取初始点，不仿取第一个结点作为开始结点
 *并采用冒泡法寻找最小的元素
 */
 public int getLittleValue(int[][] b,int[] count,int[][] tree)throws IOException{
   int recoder = 10000;
   int len = count.length;
   int iflag = 0;
   int jflag = 0;
   int flag = 1;
   for (int i = 0; i < len; i++) { //将count中记录的所有记录行，扫描一遍
     if (count[i] == 1) {
       for (int j = 1; j < len; j++) {
         if (count[j] == 1) { //如果count中记录元素，说明此结点不在所选之中
            continue;
          } //if
         else { //冒泡法找最小元素
           if((recoder > b[i][j]) && (b[i][j] != 0)){
             recoder = b[i][j];
             iflag = i;
             jflag = j;
            }
         } //else
       } //for
     } //if
   } //for
   if(recoder == 10000){
           System.out.println("此图不连通,没有最小生成树！");
           flag = 0;
   }
   cop++;
   count[jflag] = 1; //将最小元素结点记录在count中
   tree[iflag][jflag] = recoder; //将结点连接的边放在最小生成树矩阵中
   tree[jflag][iflag] = recoder;//图为对称
   return flag;
 }
 public void getLittleTree()throws IOException{
	 while (cop != dim) {
       if(getLittleValue(edge, count, tree) == 1){
                   ;
           }
           else{
                   break;
           }
     }
	 if(cop == dim){
		 result();
	 }
 }
 public void result ()throws IOException ,FileNotFoundException{
     for (int i = 0; i < dim; i++) {
       for (int j = 0; j < dim; j++) {
         fw.write(Integer.toOctalString(tree[i][j]).getBytes("ISO-8859-1"));
		 fw.write(" ".getBytes());
	//	 bos.writeChars(" ");
		 System.out.print(tree[i][j]+" ");
       } //for
         fw.write("\n".getBytes());
		System.out.print("\n");
     } //for
	    fw.close();//关闭输出流
   }
   /*
    * 测试结果是否正确
    */
   public static void main(String args[])throws IOException{
     GetLittleTree gt = new GetLittleTree();
     gt.getLittleTree(); 
  }
}