weightedgraph.java

最短路径和哈密顿通路

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;
import java.net.*;
import java.io.*;

public class WeightedGraph extends Graph{
	
	protected int[][]weights;
	
	protected int[][]pre;
	protected int[][]shortpath;
	protected boolean[]nodeFound;
	
	protected int[][]shortestpath;
	protected int[][]hampath;
	
	protected Stack<Integer> stack;	

	
	public WeightedGraph()
	{
		super();
		weights=new int[super.maxSize][super.maxSize];
		for(int i=0; i<super.maxSize; i++)
			for (int j=0; j<super.maxSize; j++)
			{
				if(i==j)
					weights[i][i]=0;
				else
					weights[i][j]=super.infinity;
			}
	}
	
	public WeightedGraph(int size)
	{
		super(size);
		weights=new int[super.maxSize][super.maxSize];
		for(int i=0; i<super.maxSize; i++)
			for (int j=0; j<super.maxSize; j++)
			{
				if(i==j)
					weights[i][i]=0;
				else
					weights[i][j]=super.infinity;
			}
	}
	
	public void createWeightedGraph() throws NumberFormatException, IOException
	{
		StringTokenizer tokenizer;
		
		int index;
		int vertex;
		int adjacentVertex;
		int edge;
		
		URL url=WeightedGraph.class.getResource("info.txt");
		InputStream in=url.openStream();
		BufferedReader infile=new BufferedReader(new InputStreamReader(in));
		
		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());
			edge=Integer.parseInt(tokenizer.nextToken());
			
			while(adjacentVertex!=-999 && edge!=-999)
			{
				graph[vertex].insertLast(new IntElement(adjacentVertex));
				weights[vertex][adjacentVertex]=edge;
				if(tokenizer.hasMoreTokens())
					adjacentVertex=Integer.parseInt(tokenizer.nextToken());
				if(tokenizer.hasMoreTokens())
					edge=Integer.parseInt(tokenizer.nextToken());
			}
		}
	}

	public int GetFirstNeighbour(int v,boolean[]visited,int [][]pre)
	{
		int alLength;
		int w;
		IntElement[] adjacencyList;
		adjacencyList=new IntElement[gSize];
		alLength=graph[v].getAdjacentVertices(adjacencyList);
		if(alLength<=0)
		{
			return -1;
		}
		else{
			for(int index=0; index<alLength; index++)
			{
				w=adjacencyList[index].getNum();
				if(!visited[w] && pre[v][w]==0)
					return w;
			}
			return -1;
		}
	}
	//测试用的辅助函数
/*	public void test(int v)
	{
		int alLength;
		int w;
		IntElement[] adjacencyList;
		adjacencyList=new IntElement[gSize];
		alLength=graph[v].getAdjacentVertices(adjacencyList);
		System.out.print("alLength: "+alLength);
		System.out.println();
		System.out.print(v+":  ");
		for(int i=0; i<alLength; i++)
		{
			System.out.print(adjacencyList[i].getNum()+" ");
		}
		System.out.println();
	}*/
	
	public void findAllPath(int v,int u)
	{
		
		pre=new int[gSize][gSize];
		for(int i=0; i<gSize;  i++)
		{
			for(int j=0; j<gSize; j++)
				pre[i][j]=0;
		}
		int ii=0;
		int mm=0;
		stack=new Stack<Integer>();

		shortpath=new int[100][gSize];
		for(int i=0; i<100; i++)
			for(int j=0; j<gSize; j++)
				shortpath[i][j]=-1;
		boolean []nodeFound=new boolean[gSize];
		for(int i=0; i<gSize; i++)
		{
			nodeFound[i]=false;
		}
		stack.push(v);
		nodeFound[v]=true;
		int temp;
		int pop;
		int k=v;
		int count=0;
		int fnb=this.GetFirstNeighbour(v,nodeFound,pre);
		int num=0;
		while(true)
		{
			num++;
			if(fnb==-1)
			{
				pop=stack.pop();
				
				nodeFound[pop]=false;
				for(int p=0; p<gSize; p++)
				{
					pre[pop][p]=0;
				}
		//		System.out.println("pop: "+pop);
				if(stack.isEmpty()==true)
					return;
				else
				{
					temp=stack.peek();
					k=stack.peek();
				//	System.out.println("-1temp: "+temp);
					fnb=this.GetFirstNeighbour(temp,nodeFound,pre);
				//	System.out.println("-1fnb: "+fnb);
				}
				
			}
			else
			{
				if(fnb==u)
				{
					k=stack.peek();
					stack.push(u);
					nodeFound[u]=true;
					pre[k][u]=-1;
					count=stack.size();
					
			//		System.out.println("路径"+mm+": ");
					
			//		System.out.print(stack);
					
			//		System.out.println();
					
					for(int p=0; p<count; p++)
					{
						shortpath[mm][p]=stack.elementAt(p);
					}
					mm++;
					
					stack.pop();
					nodeFound[u]=false;
					if(stack.isEmpty()==true)
						return;
					else
					{
						temp=stack.peek();
				//		System.out.println("utemp: "+temp);
						fnb=this.GetFirstNeighbour(temp,nodeFound,pre);
				//		System.out.println("ufnb: "+fnb);
					}
				}
				else
				{
					stack.push(fnb);
					nodeFound[fnb]=true;
					pre[k][fnb]=-1;
					k=fnb;
					temp=fnb;
					fnb=this.GetFirstNeighbour(temp,nodeFound,pre);
				//	System.out.println("fnb: "+fnb);
				}
			}
		}
	}
	
	public void findShortestPath(int v,int u)
	{
		shortestpath=new int[100][gSize];
		for(int i=0; i<100; i++)
		{
			for(int j=0; j<gSize; j++)
				shortestpath[i][j]=-1;
		}
		findAllPath(v,u);
		int []temp=new int[100];
		for(int i=0; i<temp.length; i++)
			temp[i]=0;
		
		for(int i=0; i<100; i++)
		{
			if(shortpath[i][0]!=-1)
			{
				for(int j=0; j<gSize-1; j++)
				{
					if(shortpath[i][j]!=-1 && shortpath[i][j+1]!=-1)
						temp[i]+=weights[shortpath[i][j]][shortpath[i][j+1]];
				}
	//			System.out.println("temp[i]"+temp[i]);
			}
		}
		
		int min=temp[0];
		
		for(int i=0; i<temp.length; i++)
		{
			if(temp[i]!=0)
			{
				if(min>temp[i])
					min=temp[i];
			}
		}
		
		System.out.println("最短路径为：");
		
		for(int i=0; i<temp.length; i++)
		{
			if(temp[i]!=0)
			{
				if(temp[i]==min)
				{
					for(int j=0; j<gSize; j++)
					{
						if(shortpath[i][j]!=-1)
						{
							shortestpath[i][j]=shortpath[i][j];
							System.out.print(shortestpath[i][j]+"  ");
						}
					}
					System.out.println();
				}
			}
		}
	}
	
	public void findHamPath(int v,int u)
	{
		hampath=new int[100][gSize];
		for(int i=0; i<100; i++)
		{
			for(int j=0; j<gSize; j++)
				hampath[i][j]=-1;
		}
		
		findAllPath(v,u);
		System.out.println("哈密顿通路路径：");
		
		for(int i=0; i<100; i++)
		{
			if(shortpath[i][gSize-1]!=-1)
			{
				for(int j=0; j<gSize; j++)
				{
					hampath[i][j]=shortpath[i][j];
					System.out.print(hampath[i][j]+"  ");
				}
				System.out.println();
			}
		}
	}
}