几个常用的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("该图无圈"); } } }