graph.java

最短路径和哈密顿通路

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Graph {
	protected final int infinity=100000;
	protected int maxSize;
	protected int gSize;
	protected LinkedListGraph[] graph;
	public Graph()
	{
		int k=0;
		maxSize=100;
		gSize=0;
		graph=new LinkedListGraph[maxSize];
		for(int i=0; i<maxSize; i++)
			graph[i]=new LinkedListGraph();
	}
	public Graph(int size)
	{
		int k=0;
		maxSize=size;
		gSize=0;
		graph=new LinkedListGraph[maxSize];
		for(int i=0; i<maxSize; i++)
			graph[i]=new LinkedListGraph();
	}
	public boolean isEmpty()
	{
		return (gSize==0);
	}
	public void creatGraph()throws IOException,FileNotFoundException
	{
		BufferedReader keyboard=new BufferedReader(new InputStreamReader(System.in));
		String fileName;
		StringTokenizer tokenizer;
		
		int index;
		int vertex;
		int adjacentVertex;
		
		if(gSize!=0)
			clearGraph();
		
		BufferedReader infile=new BufferedReader(new FileReader("D:\\Jpro\\Travel\\info.txt"));
		
		gSize=Integer.parseInt(infile.readLine());
		for(index=0; index<gSize; index++)
		{
			tokenizer=new StringTokenizer(infile.readLine());
			vertex=Integer.parseInt(tokenizer.nextToken());
			adjacentVertex=Integer.parseInt(tokenizer.nextToken());
			
			while(adjacentVertex!=-999)
			{
				graph[vertex].insertLast(new IntElement(adjacentVertex));
				adjacentVertex=Integer.parseInt(tokenizer.nextToken());
			}
		}
	}
	private void clearGraph() {
		// TODO Auto-generated method stub
		int index;
		for(index=0; index<gSize; index++)
			graph[index]=null;
		gSize=0;
	}
	private void dft(int v,boolean []visited)
	{
		int w;
		IntElement[]adjacencyList;
		adjacencyList=new IntElement[gSize];
		int alLength;
		visited[v]=true;
		alLength=graph[v].getAdjacentVertices(adjacencyList);
		for(int index=0; index<alLength; index++)
		{
			w=adjacencyList[index].getNum();
			if(!visited[w])
				dft(w,visited);
		}
	}
	public void depthFirstTraversal()
	{
		boolean[]visited;
		visited=new boolean[gSize];
		int index;
		for(index=0; index<gSize; index++)
			visited[index]=false;
		for(index=0; index<gSize; index++)
			if(!visited[index])
				dft(index,visited);
	}
	public void dftAtVertex(int vertex)
	{
		boolean[]visited;
		visited=new boolean[gSize];
		for(int index=0; index<gSize; index++)
			visited[index]=false;
		dft(vertex,visited);
	}
}