neweular.java

计算机算法程序

package liu;

import java.util.Random;

import javax.swing.JOptionPane;

public class NewEular {

	private int[][] eage;//存放边值，0无边，1有边，>1标记给边标的值
	private int[] Degree;//存放节点的度
    public void RandMap(int size)//随机生成连通图
    { 
    	eage = new int [size][size];
    	Degree = new int[size];
    	int i =  2;
    	eage[0][1] = 1;
    	eage[1][0] = 1;
    	Degree[0] = 1;
    	Degree[1] = 1;//首先把0和1联起来
    	Random rand = new Random();
    	while(i < size) //随机产生边，连起来
    	{ 
    		int k = rand.nextInt(i);
    		eage[i][k] = 1;
    		eage[k][i] = 1;
    		Degree[i]++; //各自节点的度数加1
    		Degree[k]++;
    		i++;
    	}
    
    }
    public void StructEular(int size) //构造欧拉图
    { 
    	int[] f = new int [size];//存放度数为奇数的节点号
    	int k = 0;
    	int m = -1;
    	for(int i = 0;i < size;i++)//把度数为奇数的节点存放在f数组
    	{ 
    		if(Degree[i]%2!=0)
    			f[k++] = i;
    	}
    	for(int i = 0;i < k;i=i+2)//把度数为奇数的边连起来
    	{
    		if(eage[f[i]][f[i+1]] == 1)//如果两边本来有边
    		{ 
    			m = -1;//m保存跟这两点无边的节点
    			for(int j = 0;j < size;j++)//找一个跟这两个节点不相邻的节点连起来
    			{	
    				if(j!=f[i+1] && j!=f[i] && eage[j][f[i]]==0 && eage[j][f[i+1]]==0)
    				{ 
    					m = j;
    				    break;
    				}
    			}
    			eage[f[i]][m] = 1;
    			eage[m][f[i]] = 1;
    			eage[f[i+1]][m] = 1;
    			eage[m][f[i+1]] = 1;
    		}
    		else //如果两点无边就直接连起来
    		{ 
    			eage[f[i]][f[i+1]] = 1;
    			eage[f[i+1]][f[i]] = 1;
    		}
    	}
    }
    public void printf(int size) //打印图各边的矩阵
    { 
    	for(int i = 0;i < size;i++)
    	{
    		for(int j = 0;j < size;j++)
    	       System.out.print(eage[i][j]);
    		System.out.println();
    	}
    }
	public void Euler(int n )   //欧拉路算法
	{
	  int[] f = new int[n*n];//定义一个队列
	  int rear = 0;  //队尾指针
	  f[rear] = 0;
	  rear++;
	  int first = 0;//队首指针
	  int roadsign = 2; // 路的标志
	  int i = 0;
	  int v = f[rear - 1]; //第一个点入队列
	  //eage[i][j]=1代表有边，eage[i][j]代表已经做过标志的边
	  while(first<=rear) //当队列中有元素时，入队列
	  {  
	     for( ;i < n;)
	     { 
	    	 if(eage[v][i]==1) //有边就入队列
	    	 { 
	    		 f[rear] = i;
	    		 eage[v][i] = roadsign; //至标志
	    		 eage[i][v] = roadsign; 
	    		 rear++; //队列后移
	    		 v = i;
	    		 i = 0;
	    	 }
	    	 else i++;  //找下一个
	     }
	     if(IsEage(f[first],n)) //如果存在没有做标志的边，继续入栈
	     { 
	    	 v = f[first];
	    	 i = 0;
	    	 roadsign++;
	     }//边的权值标志加1
	     else  first++;  //在队列中找下一个
			
	  }
	  TraverEular(n); //遍历欧拉图
	  System.out.println();
	  if(!HaveEage(n))  //看是否还有边，无边则结果正确
		  System.out.print("the result is correct!");
	  else System.out.print("the result is wrong!");
	}
	public boolean IsEage(int v,int n)//判断v节点是否还有没标的边
	{ 
		int iseage = 0; 
		for(int i = 0;i < n;i++) //1代表有边
			if(eage[v][i]==1) //若有则置标志为一
				iseage = 1;
		if(iseage == 1) return true;
		else return false;
	}
	public boolean HaveEage(int n) //检查是否还有边
	{ 
		int sign = 0;
		for(int i = 0;i < n;i++)
			for(int j = 0;j < n;j++)
			  if(eage[i][j] > 0) { sign = 1;} //有边则把标志置为1
	    if(sign == 1) return true; //有边，返回结果真
	    else return false; //无边，返回结果假
	}
	public void TraverEular(int n)  //走欧拉回路
	{ 
	  int max = 0;  //记录边的标志权值
	  int v = 0;   //从起始点开始
	  System.out.println("the circuit of Eular is:");
	  System.out.print(v);
	  do
	   { 
		  int k = 0;
		  max = 0; 
		  for(int i = 0;i < n;i++)
			  if(eage[v][i]>max)   //找出权值最大的边走
			  { 
				  max = eage[v][i];
			      k = i;
			  }
		  eage[v][k] = 0; //走过的边置0
		  eage[k][v] = 0;
		  v = k; //继续向前走
		  System.out.print("->"+v);
	   }while(IsHaveEage(0,n)); //直到走回去,并且0节点不可以在走
		  
	}
	public boolean IsHaveEage(int v,int n)//判断v是否有没走完的边
	{ 
		int sign = 0;
		for(int i = 0;i < n;i++)
			if(eage[v][i] > 1) sign = 1;
		if(sign == 1) return true;
		else return false;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	int size;
	String s = JOptionPane.showInputDialog("Please input the numble of node:");		
	size  = Integer.parseInt(s); //输入节点个数
    NewEular oula = new NewEular();
    oula.RandMap(size);//随机生成连通图
 	oula.printf(size);//打印出来
 	System.out.println("the random eular map is:");
 	oula.StructEular(size);//把连通图改造成欧拉图
 	oula.printf(size);//打印出来
	oula.Euler(size);//找出欧拉回路
	}

}