graphtheory.java

用Java开发的实用数学建模程序 简单易懂 初学者可以用来学习java知识

/*
 *@(#)GraphTheory.java 2.0 2005/05/02
 *
 *清华大学　精密仪器与机械学系
 *范灿升　[e-mail]
 */

package algorithm;

import java.util.*;

import algorithm.HamiltonSort;
import ADT.BinaryTree;

/**
 *这个类是图论的类，里面包含一些图论常见的算法。
 *@version	2.0, 2005/04/30
 *@author	范灿升
 *@see	Modeling
 *@see	input.GraphInput
 */

public class GraphTheory
{
	private int[][] adjacentMatrix;//邻接矩阵
	private int[][] incidenceMatrix;//关联矩阵
	private int[][] weightMatrix;//权矩阵
	private int matrixType;//构造时矩阵的类型
	
	/**
	 *说明构造方法所传过来的矩阵是邻接矩阵。
	 */
	public final static int ADJACENT=1;
	
	/**
	 *说明构造方法所传过来的矩阵是关联矩阵。
	 */
	public final static int INCIDENCE=2;
	
	/**
	 *说明构造方法所传过来的矩阵是权矩阵。
	 */
	public final static int WEIGHT=3;
	
	/**
	 *图的结点数。
	 */
	public int n;
	
	/**
	 *图的边数。
	 */
	public int m;
	
	/**
	 *用所给矩阵生成一个图。
	 *@param	matrix		图所对应的矩阵，这个矩阵在GraphTheory类中产生克隆副本，GraphTheory的成员方法不会对该矩阵生产影响。
	 *@param	matrixType	矩阵类型，可以为{@link #ADJACENT}、{@link #INCIDENCE}、{@link #WEIGHT}。
	 */
	public GraphTheory(int[][] matrix,int matrixType)
	{
		this.matrixType=matrixType;
		switch(matrixType)
		{
			case ADJACENT:
				adjacentMatrix=(int[][])matrix.clone();
				break;
			case INCIDENCE:
				incidenceMatrix=(int[][])matrix.clone();
				break;
			case WEIGHT:
				weightMatrix=(int[][])matrix.clone();
				break;
		}
	}
	
	/**
	 *Dijkstra算法，根据权矩阵计算图中任意两结点间的最短路。
	 *<p>计算最短路的图必须是正权有向图。
	 *<p>受int大小的限制，权值必须小于Integer.MAX_VALUE，即2147483647。
	 *对于无向图，用户必须先把它的权矩阵转换成有向图的权矩阵。
	 *@param	start	开始结点，结点编号从0开始
	 *@param	end		结束结点，结点编号从0开始
	 *@return	Vector类的一个实例，该Vector中只有三个元素，int[]、Integer及int[]的实例。
	 *			<p>其中第一int[]是从start结点到任一结点的最短路径矩阵path，int[end]中所存放的是从start到end的最短路径中end的前一结点。
	 *			<p>Integer是最短路径的长度的整型数封装。当Integer为-1时，说明不存在从start到end的路径。
	 *			<p>第二个int[]是从start到各结点（包括自身）的最短路径长度len，上面的Integer就是对int[]中第end个元素的封装。
	 *			如果Integer为-1，则len中部分元素还保持初值Integer.MAX_VALUE。
	 *			<p>如果构造该类时的矩阵不是权矩阵，或者不是图不是正权图，则返回null。
	 */
	public Vector dijkstra(int start,int end)
	{
		int i,j;//循环变量
		int ii,jj;//算法中用
		int min;
		int count;//计算下面的undetermined数组中还有多少元素为true
		int lastCount=-1;//赋值为-1，下面if语句的lastCount==count第一次就肯定不会满足
		boolean done;//用于检查是否可以跳出算法中的循环
		n=weightMatrix.length;
		if(matrixType!=WEIGHT)
			return null;
		//不是权矩阵就返回null
		
		n=weightMatrix.length;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(weightMatrix[i][j]<0)
					return null;
			}
		}
		//如果权矩阵含有小于0的元素就返回null
		
		int[] path=new int[n];
		int[] len=new int[n];
		for(i=0;i<n;i++)
			path[i]=start;
		for(j=0;j<n;j++)
		{
			if(weightMatrix[start][j]>0)//从start结点到j有道路
				len[j]=weightMatrix[start][j];
			else
				len[j]=Integer.MAX_VALUE;
		}
		len[start]=0;//从start到start的长度当然为0
		
		boolean[] undetermined=new boolean[n];
		//true表示还没有找到最短路
		for(i=0;i<n;i++)
			undetermined[i]=true;
		undetermined[start]=false;
		//初始化
		
		jj=start;
		while(true)
		{
			min=Integer.MAX_VALUE;
			for(ii=0;ii<n;ii++)
			{
				if(undetermined[ii]==true)
				{
					if(len[ii]<min)
					{
						jj=ii;
						min=len[ii];
					}
				}
			}
			//寻找len[ii]的最小值，并对取最小值时的ii用jj标记
			undetermined[jj]=false;
			
			done=true;
			count=0;
			for(i=0;i<n;i++)
			{
				if(undetermined[i]==true)
				{
					done=false;//undetermined中还有数，不能跳出while循环
					count++;
				}
			}
			if(lastCount==count)
			//两次undetermined中为true的元素数目相等，说明下面的for循环什么不起作用，不存在start到end的路径
				break;
			lastCount=count;
			if(done==true)
				break;
			//判断是否可以跳出while循环
			
			for(i=0;i<n;i++)
			{
				if((weightMatrix[jj][i]>0)&&(undetermined[i]==true))
				//jj的后继结点，且在undetermined中
				{
					if(len[i]>len[jj]+weightMatrix[jj][i])
					{
						len[i]=len[jj]+weightMatrix[jj][i];
						path[i]=jj;
					}
				}
			}//len[jj]始终不是Integer.MAX_VALUE
		}
		//完成算法的主体部分
		
		//现在len和path都有了，可以进行封装和返回了
		if(len[end]==Integer.MAX_VALUE)
			len[end]=-1;
		Integer solutionLength=new Integer(len[end]);
		Vector vector=new Vector();
		vector.add(path);
		vector.add(solutionLength);
		vector.add(len);
		return vector;
	}
	
	
	/**
	 *用分支与界法求解旅行商问题。
	 *<p>计算旅行商问题的图必须是无向完全图。由于无向图的权矩阵是对称阵，因此该方法不检查权矩阵是否真的为对称阵，
	 *而是直接使用权矩阵对角线以上的元素，对权矩阵对称性的检查就在输入端完成。
	 *<p>图的结点数不能小于3。
	 *<p>受int大小的限制，权值必须小于Integer.MAX_VALUE，即2147483647。
	 *@return	整型数组int[]，其中int[].length==n+1，int[0]是哈密顿圈的长度，从int[1]到int[n]记录哈密顿圈依次经过的结点。
	 *			结点从0从开始。
	 *			<p>以下三种情况返回null：该图不是完全图、结点数小于3、构造GraphTheory类时matrixType不为WEIGHT。
	 */
	public int[] hamilton()
	{
		int i,j,k;
		n=weightMatrix.length;
		if((n<3)||(matrixType!=WEIGHT))
			return null;
		int[][] edge=new int[(n*n-n)/2][5];
		//边集合，每条边包含五个元素，分别为边权、结点、结点、索引、由边生成路径时是否已作标记
		k=0;
		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				if(weightMatrix[i][j]==0)
					return null;
				edge[k][0]=weightMatrix[i][j];
				edge[k][1]=i;
				edge[k][2]=j;
				edge[k][4]=0;//未取该边
				k++;
			}
		}
		//检查是否为完全图，同时完成对待排序边集合的初始化
		
		Arrays.sort(edge,new HamiltonSort());
		for(i=0;i<edge.length;i++)
			edge[i][3]=i;//为edge设置索引位，即排好序后在队列中的顺序
		int len=Integer.MAX_VALUE;
		//排序，设置索引和置初始边界
		
		int[][] stack=new int[n][5];//用来存放栈中的边
		int currentLength=0;
		int popCount;
		int[] nodeCount=new int[n];//标记各结点出现的次数
		for(i=0;i<n;i++)
			nodeCount[i]=0;
		for(i=0;i<n;i++)
		{
			stack[i]=edge[i];
			currentLength+=edge[i][0];
		}
		for(i=0;i<n;i++)
		{
			nodeCount[stack[i][1]]++;
			nodeCount[stack[i][2]]++;
		}
		popCount=n;//popCount是从后面数起索引连续的元素的个数
		
		int index;
		boolean cycled;//判断是否构成哈密顿圈
		int[][] result=new int[n][5];//记录最终结果
		while(true)
		{
			cycled=true;
			for(i=0;i<n;i++)
			{
				if(nodeCount[i]!=2)
				{
					cycled=false;
					break;
				}
			}
			
			if(cycled&&(currentLength<len)&&(popCount!=n))
			//stack中的元素构成哈密顿圈且该圈长度比原来的圈小，同时stack还可以往后退
			{
				len=currentLength;
				for(k=0;k<n;k++)
					result[k]=stack[k];
				index=stack[n-1-popCount][3]+1;//后面连续在stack中的前一位的下一个索引
				for(j=n-1-popCount;j<n;j++)
				//开始新分支
				{
					if(index>=edge.length)
						break;//不能再退就返回
					
					currentLength-=stack[j][0];
					nodeCount[stack[j][1]]--;
					nodeCount[stack[j][2]]--;
					
					stack[j]=edge[index];
					//stack[j]已被它对应的edge后面的边替换
					index++;
					
					currentLength+=stack[j][0];
					nodeCount[stack[j][1]]++;
					nodeCount[stack[j][2]]++;
				}
			}
			else if(cycled&&(currentLength<len)&&(popCount==n))
			//当stack不能往后退时
			{
				len=currentLength;
				for(k=0;k<n;k++)
					result[k]=stack[k];
				break;
			}
			else if(currentLength>=len)
			//长度比界限大也要开始新分支
			{
				index=stack[n-1-popCount][3]+1;
				for(j=n-1-popCount;j<n;j++)
				//开始新分支
				{
					if(index>=edge.length)
						break;
					
					currentLength-=stack[j][0];
					nodeCount[stack[j][1]]--;
					nodeCount[stack[j][2]]--;
					
					stack[j]=edge[index];
					//stack[j]已被它对应的edge后面的边替换
					index++;
					
					currentLength+=stack[j][0];
					nodeCount[stack[j][1]]++;
					nodeCount[stack[j][2]]++;
				}
			}
			else
			//相当于else if((!cycled)&&(currentLength<len))
			//长度比界限小，同时不构成哈密顿圈，可以继续向下搜
			{
				for(i=0;i<n;i++)
				//从stack最后一个元素起，依次往edge后面退，只要有一个可退就中断
				{
					if(stack[n-1-i][3]<(edge.length-1-i))//防止已经有元素退到edge的最后
					{
						currentLength-=stack[n-1-i][0];
						nodeCount[stack[n-1-i][1]]--;
						nodeCount[stack[n-1-i][2]]--;
						
						index=stack[n-1-i][3];
						index++;
						stack[n-1-i]=edge[index];
						
						currentLength+=stack[n-1-i][0];
						nodeCount[stack[n-1-i][1]]++;
						nodeCount[stack[n-1-i][2]]++;
						
						break;
					}
				}
			}
			
			popCount=1;
			for(i=n-1;i>0;i--)
			//更新popCount
			//由于是和stack[i]的前一个比较，所以i不能为0
			{
				if(stack[i][3]==(stack[i-1][3]+1))//连续
					popCount++;
				else
					break;//不马上跳出循环的话popCount的记录就不准
			}
			
			if((popCount==n)&&(len<Integer.MAX_VALUE))
				break;//全部连续，剩下的分支只会比len大，可以跳出循环
		}
		//完成主体算法
		//stack中的元素就是构成最小哈密顿圈的边
		
		
		int[] path=new int[n+1];
		path[0]=len;
		path[1]=result[0][1];
		for(i=1;i<path.length-1;i++)
		{
			for(j=0;j<result.length;j++)
			{
				if(result[j][1]==path[i]&&result[j][4]==0)
				{
					path[i+1]=result[j][2];
					result[j][4]=1;
					break;
				}
				if(result[j][2]==path[i]&&result[j][4]==0)
				{
					path[i+1]=result[j][1];
					result[j][4]=1;
					break;
				}
			}
		}
		return path;
		//生成路径并返回
	}
	
	/**
	 *Huffman算法，根据所给树的结点链表对构造Huffman树的过程作一次递归。
	 *<p>构造的过程是把权最小的两个结点合并为一个结点。
	 *@param	binTree	等待构树的结点链表。
	 *			<p>最终得到的binTree是这样一个链表：该链表中只有一个元素，为Huffman树的根结点，是一个二叉树结点类，
	 *			根据该根结点，可以找到二叉树的全部结点。
	 *			<p>需要注意的是：生成Huffman树的过程是对方法自身的不断递归调用，
	 *			因此得到的BinaryTree中的info域并未被初始化。
	 *			<p>要得到含有路径信息的Huffman树，应调用huffman方法。
	 *@see	#huffman
	 *@see	#generateHuffmanPath
	 */
	public static void generateHuffmanTree(LinkedList binTree)
	{
		if(binTree.size()==1)
			return;
		else
		{
			Collections.sort(binTree,new BinaryTreeSort());
			BinaryTree tempLeft=(BinaryTree)binTree.removeFirst();
			BinaryTree tempRight=(BinaryTree)binTree.removeFirst();
			BinaryTree tempParent=new BinaryTree();
			
			tempParent.leftChild=tempLeft;
			tempParent.rightChild=tempRight;
			tempParent.weight=tempLeft.weight+tempRight.weight;
			tempLeft.parent=tempParent;
			tempRight.parent=tempParent;
			
			binTree.addFirst(tempParent);
			generateHuffmanTree(binTree);
		}
	}
	
	/**
	 *根据已生成的Huffman树生成树中各结点的路径。
	 *<p>由于Huffman树是二叉树，因此用0和1表示从根结点到当前结点的路径，
	 *0表示从父结点向左走得到下一结点，1表示从父结点向右走得到下一结点。
	 *@param	currentNode	当前结点
	 *@see	#huffman
	 *@see	#generateHuffmanTree
	 */
	public static void generateHuffmanPath(BinaryTree currentNode)
	{
		if(currentNode.leftChild==null && currentNode.rightChild==null)
			return;
		else
		{
			currentNode.leftChild.info=new StringBuffer(currentNode.info.toString());
			currentNode.leftChild.info.append("0");
			generateHuffmanPath(currentNode.leftChild);
			
			currentNode.rightChild.info=new StringBuffer(currentNode.info.toString());
			currentNode.rightChild.info.append("1");
			generateHuffmanPath(currentNode.rightChild);
		}
	}
	
	/**
	 *Huffman算法，根据所给树叶结点的权构造最优二叉树，该树称为Huffman树。
	 *@param	leafVertex	树叶结点的权数组
	 *@return	Huffman树的树叶结点数组，每个结点中都含有从根到该树叶结点的路径。
	 *			<p>0表示向左，1表示向右。
	 *@see	#generateHuffmanTree
	 *@see	#generateHuffmanPath
	 */
	public static BinaryTree[] huffman(int[] leafVertex)
	{
		int n=leafVertex.length;
		int i;
		BinaryTree[] binTree=new BinaryTree[n];
		LinkedList binTreeList=new LinkedList();
		for(i=0;i<n;i++)
		{
			binTree[i]=new BinaryTree();
			binTree[i].weight=leafVertex[i];
			binTree[i].id=i;
			binTreeList.add(binTree[i]);
		}
		
		generateHuffmanTree(binTreeList);
		BinaryTree root=(BinaryTree)binTreeList.get(0);
		root.info=new StringBuffer();
		generateHuffmanPath(root);
		return binTree;
	}
}