graphsearch.java

集束搜索,经典算法

/*	Name: GraphSearch.java
 *	Author: Liu Lizhe [e-mail]
 *	Date Created: November 11,2004
 *	Description: A graph-search programme using adjacency matrix input &
 *	 				beam search algorithm
 */


import java.io.*;
import com.LiuLizhe.util.Queue;

public class GraphSearch{
	public static void main(String[] args) throws IOException{

		//Prompt displayed on screen
		System.out.println("---------------------USAGE---------------------");
		System.out.println("The input file (.txt) is like this:");
		System.out.println("8\n1\n8");
		System.out.println("01100000");
		System.out.println("10011000");
		System.out.println("10000110");
		System.out.println("01000001");
		System.out.println("01000001");
		System.out.println("00100010");
		System.out.println("00100100");
		System.out.println("00011000");
		System.out.println("The first line is the total number of vertexes in your graph.");
		System.out.println("The second line is the initial vertex.");
		System.out.println("The third line is the target vertex.");
		System.out.println("And the following is the adjacency matrix, in which '0' stands for 'not adjacent' and '1' stands for 'adjacent'.");
		System.out.println("Please enter the path of your input file, e.g. E:\\Java\\GraphSearch\\AdjMatrix.txt, and the default directory is where this program is located:");
		System.out.print(">>");
		
		//Reading input by file
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		String path = in.readLine();
		System.out.println("The searching process is:");
		in = new BufferedReader(new FileReader(path));
		String s=in.readLine();
		int VertexNum=Integer.valueOf(s).intValue();
		String InitialVertex = in.readLine();
		String TargetVertex = in.readLine();
		
		//Create adjacency matrix			
		char[][] AdjMatrix=new char[VertexNum][VertexNum];
		for (int i=0; i<VertexNum; i++){
			s = in.readLine();
			for (int j = 0; j < s.length(); j++) {
				AdjMatrix[i][j] = s.charAt(j);
			}
		}
		in.close();

		//Initialization
		boolean[] visited=new boolean[VertexNum];
		for (int i = 0; i < VertexNum; i++){
			visited[i]=false;
		}
		Queue open = new Queue();
		Queue closed = new Queue();
		open.enQueue(InitialVertex);

		//Search the graph to find a path
		boolean loop = true;
		while (loop) {
			String CurrentVertex = (String)open.deQueue();
			closed.enQueue(CurrentVertex);
			int i = Integer.valueOf(CurrentVertex).intValue() - 1;
			visited[i]=true;
			for (int j = 0; j < VertexNum; j++)
				if ((AdjMatrix[i][j]=='1') && (!visited[j]))
					if (j == Integer.valueOf(TargetVertex).intValue() - 1) {
						closed.enQueue(TargetVertex);
						for (int k = 0; k < closed.size(); k++)
							System.out.print((String)closed.get(k)+' ');
						loop = false;
					} else {
						open.enQueue(String.valueOf(j+1));
					}
		}
		System.out.println("\n");
	}
}