bfs.java

包括冒泡排序

/**
 * 用BFS算法实现求图的最短路径
 * @author jok
 * @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 Bfs {
  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 length =0;//存放最短路径的长度
  private ArrayList list2 = new ArrayList();//存放最短路径经过的结点
  public void readGraph() {
    byte[] b = new byte[100];
    String str;
    try {
      File file = new File("D:\\eclipse-java-europa-win32\\jok\\Lg\\graph.txt");
      BufferedReader br = new BufferedReader(new FileReader(file));
      while((str=br.readLine())!=null) {
        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();
    }  
    System.out.println("读取到的内容为：");
    for(int i = 0;i<lists.size();i++) {
      System.out.println(lists.get(i).get(0)+","+lists.get(i).get(1));
    }
  }
  public void printGraph() {
    System.out.println("用链表表示为：");
    Iterator itr = set.iterator();
    while(itr.hasNext()) {
      list1.add(itr.next());
    }
    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);
      StringBuffer sb = new StringBuffer();
      for(int h=0;h<list2.size();h++) {
        sb.append(list2.get(h));
        sb.append(",");
      }
      String str;
      str=new String(sb);
      System.out.println(list1.get(i)+"--"+str);
    }
  }
  public void shortestPath(Character begin,Character end) {
    list2.add(begin);
    Set set = map.keySet();
    Iterator itr = set.iterator();
    while(itr.hasNext()) {
      Character c = (Character)itr.next();
      if(c.equals(begin)) {
        ArrayList list =(ArrayList)map.get(c);
        boolean flag = false;//判断在map中是否找到结束点
        for(int j=0;j<list.size();j++) {
          if(((Character)list.get(j)).equals(end)) {
            length++;
            list2.add(end);
            flag = true;
          }
        }
        for(int j=0;j<list.size();j++) {
          if(!flag) {
            length++;
            shortestPath((Character)list.get(j),end);
          }
        }
      }
    }
  } 
  public static void main(String[] args) {
    Bfs test = new Bfs();
    test.readGraph();
    test.printGraph();
    test.shortestPath('3','4');
    System.out.println("最短路径的长度为："+test.length);
    System.out.print("最短路径经过的结点有：");
    for(int i=0;i<test.list2.size();i++) {
      System.out.print(test.list2.get(i)+" ");
    }
  }

}