testgraph.java

包括冒泡排序

/**
 * 判断一个图是否是连通图，是否是树，是否有圈
 * @author jok
 * @since 2008/12/02
 * @version 1.0
 */

package cn.com.csu.algorithm;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class TestGraph {
  private Set set = new HashSet();//用来存放所有的结点
  private ArrayList list1 = new ArrayList(); //用来存放所有的结点
  private ArrayList<ArrayList> lists = new ArrayList<ArrayList>();//存储TXT文本的信息
  private HashMap map = new HashMap(); //存放各点与其邻接点的表
  private int edgeCount = 0; //边数
  private int pointCount = 0;//点数
  private ArrayList clist = new ArrayList();//判断圈用到的
  private Set cset = new HashSet();
  private int count = 0 ;
  private int ii =0 ;
  
  /*
   * 测试是否是连通图
   */
  public boolean checkConnection(File f) {
    boolean flag = false;
    byte[] b = new byte[100];
    String str;
    try {
      
      BufferedReader br = new BufferedReader(new FileReader(f));
      while((str=br.readLine())!=null) {
        edgeCount++;
        char[] c = str.toCharArray();
        ArrayList list = new ArrayList();
        list.add(c[0]);
        list.add(c[1]);
        set.add(c[0]);
        set.add(c[1]);
        lists.add(list);
      }
    } catch (FileNotFoundException e) {
      e.printStackTrace();
    } catch (IOException e) {
      e.printStackTrace();
    }  
    Iterator itr = set.iterator();
    while(itr.hasNext()) {
      list1.add(itr.next());
    }
    pointCount = list1.size();
    for(int i = 0;i<list1.size();i++) {
      Set set2 = new HashSet();
      for(int j = 0;j<lists.size();j++) {
        if(lists.get(j).contains(list1.get(i))) {
          set2.add(lists.get(j).get(0));
          set2.add(lists.get(j).get(1));
        }
      }
      set2.remove(list1.get(i));
      ArrayList list2 = new ArrayList();
      Iterator itr2 = set2.iterator();
      while(itr2.hasNext()) {
        list2.add(itr2.next());
      }
      map.put(list1.get(i),list2);
    }
    Set set = map.keySet();
    Iterator itr2 = set.iterator();
    flag = this.test((Character)itr2.next());
    //System.out.println(flag);
    return flag;
  }
  
  /*
   * 辅助测试方法
   */
  public boolean test(Character begin) {
    
    Set set = map.keySet();
    Iterator itr2 = set.iterator();
    list1.remove(begin);
    while(itr2.hasNext()) {
      Character c = (Character)itr2.next();
      if(c.equals(begin)) {
        ArrayList list =(ArrayList)map.get(c);
        boolean flag = false;//判断在list1中是否移除了点，若移除了为true，若没移除而且list1中还有元素，则说明图不连通
        for(int j=0;j<list.size();j++) {
          if(list1.contains(list.get(j))) {
            flag = list1.remove(list.get(j));
          }
        }
        if(list1.size()==0) {
          return true;
        }
        if(!flag && list1.size()!=0) {
          return false;
        }
        for(int j=0;j<list.size();j++) {
          this.test((Character)list.get(j));
        }
        if(list1.size()==0) {
          return true;
        }
      }
     }
    return false;
  } 
  /*
   * 测试是否为树，连通且边数是点数减去1就是树
   */
  public boolean testTree(File f) {
    boolean flag = false;
    if(!this.checkConnection(f)) {
      return false;
    }else {
      if(edgeCount==pointCount-1) {
        return true;
      }
    }
    return flag;
  }
  /*
   * 测试图中是否含有圈，首先把图中一个点加入clist和cset中，依次在邻接矩阵中把相邻的点加入clist和cset中，每
   * 加一次，计数器加一，只有在计数器的值小于边数的时候，才继续加入，若clist的长度大于cset的长度，则有圈
   */
  public boolean testCycle(File f) {
    boolean flag = false;
    Character c= (Character)lists.get(0).get(0);
    clist.add(c);
    cset.add(c);
    flag = test2(c);
    return flag;
  }
  public boolean test2(Character c) {
    count ++;
    boolean flag =false;
    if(count < edgeCount) {
      for(int i=0;i<lists.size();i++) {
        if(lists.get(i).get(0).equals(c)) {
          clist.add(lists.get(i).get(1));
          cset.add(lists.get(i).get(1));
          test2((Character)lists.get(i).get(1));
        }
      }
    }
    if(cset.size()<clist.size()) {
      return true;
    }
    return flag;
  }
  public static void main(String args[]) {
    TestGraph t = new TestGraph();
    TestGraph t2 = new TestGraph();
    File f = new File("D:\\eclipse-java-europa-win32\\jok\\Lg\\graph.txt");
    boolean b2 = t.testTree(f);
    boolean b1 = t.checkConnection(f);
    if(b1) {
      System.out.println("该图是连通的");
    } else {
      System.out.println("该图是不连通的");
    }
    if(b2) {
      System.out.println("该图是一棵树");
    } else {
      System.out.println("该图不是一棵树");
    }
    t2.checkConnection(f);
    if(t2.testCycle(f)) {
      System.out.println("该图有圈");
      System.out.print("路径是:");
      for(int i =0;i<t2.clist.size()-2;i++) {
        System.out.print(t2.clist.get(i)+",");
      }
    }else {
      System.out.println("该图无圈");
    }
    
  }
}