graph.java

一般都是求图的最小生成树

//To find a maximum spanning tree of the Graph
//无向带权图
//
//程序名称：寻找一个无向带权图的最大生成树(生成树边的权值和最大)
//程序用途：算法分析与设计上机实验
//程序作者：张焕人
//作者邮箱: [e-mail]  [e-mail]
//作者QQ：27949278
//

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.RandomAccessFile;



public class Graph
{   
	//private final static int M=65535;
	public static Vertex[] vertexList; // array of vertices
	static int[][] adjMat;
	static int VertsNum;
	public void initGraph(int num)
	{
		vertexList = new Vertex[num];
		// adjacency matrix
		adjMat = new int[num][num];
		for(int y=0; y<num; y++)      // set adjacency
			for(int x=0; x<num; x++)   //    matrix to 0
				adjMat[x][y] = 0;
	}
	
	public static String getUserCommand()
	{
		String s = "";
		try
		{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			s = br.readLine();
			
		}
		catch(IOException e)
		{
			
		}
		return s;
	}
	
	public void readGraph(){
		File currentDir = new File(".\\");
		String filename;
		String file;
		
		try {
		   System.out.print("\n\n请输入要打开的数据文件(直接回车选定默认文件graph.txt)：");
		   file=getUserCommand();
		   if (file.length()==0)
			   filename=currentDir.getCanonicalPath()+"\\"+"graph.txt";
		   else filename=currentDir.getCanonicalPath()+"\\" + file;	         
		   RandomAccessFile raf= new RandomAccessFile( filename,"r" );
							
			while(raf.length()==0) 
			{ 
				System.out.println("输入有误或相应的记录不存在！");
			    System.out.println("按任意键重新输入...");
			    file=getUserCommand();
				   if (file.length()==0)
					   filename=currentDir.getCanonicalPath()+"\\"+"graph.txt";
				   else filename=currentDir.getCanonicalPath()+"\\" + file;	         
				raf= new RandomAccessFile( filename,"r" );
			}
			
			int start,end,length;
			
			VertsNum=Integer.parseInt(raf.readLine());
			
			System.out.println("图中共有顶点数目："+VertsNum);
			initGraph(VertsNum);
			
			String tmp;  
			
			while(raf.getFilePointer()!=raf.length())
			{   
				tmp=raf.readLine();
				start=Integer.parseInt(tmp.split(" ")[0]);  //the array starts with '0'
			    end=Integer.parseInt(tmp.split(" ")[1]);   //一定要类型匹配
			    length=Integer.parseInt(tmp.split(" ")[2]);
			    adjMat[start][end]=length;
			    adjMat[end][start]=length;
			}
			System.out.println("成功打开文件"+filename);
			
			} catch (FileNotFoundException e) {
				System.out.println("相应的文件不存在! 请重新输入...");
				readGraph();
			}
			catch (IOException e) {
				e.printStackTrace();
			}
			
			vertexList=new Vertex[VertsNum];
			for(int i=0;i<VertsNum;i++)
			{
				vertexList[i]=new Vertex(""+i);
			}
			
	}
	
	public void showAdjMat()
	{   System.out.println("图的邻接矩阵表示形式如下：");
		for(int i=0;i<VertsNum;i++)
		{ 
			for(int j=0;j<VertsNum;j++)
			{   
				System.out.print(" "+adjMat[i][j]); 
			}
		    System.out.println();
		}
	}
  	
  public void Prim()
  {   
	  vertexList[0].wasVisited=true;
	  vertexList[0].distance=0;
	  vertexList[0].parent=null;
	  for(int i=1;i<VertsNum;i++)  //初始化
      {
    	vertexList[i].distance=adjMat[0][i];
    	if(vertexList[i].distance!=0) 	vertexList[i].parent=vertexList[0];
    	  else   vertexList[i].parent=null;
      }
	  
	  for(int i=1;i<VertsNum;i++)
	  {
		addEdge();  
	  }	  
	  	    
  }
  
  public void addEdge()
  {
	  int idx=0;
	  int distance=0;
	  
	  for(int i=1;i<VertsNum;i++)  //找到最短路径点u
	  {
		if(!vertexList[i].wasVisited && vertexList[i].distance>distance) 
		{
			idx=i;
		    distance=vertexList[i].distance;	
		}  
	  }
	  
	  vertexList[idx].wasVisited=true;
	  System.out.print("  "+vertexList[idx].parent.label+"——"+vertexList[idx].label);
	  
	  for(int i=1;i<VertsNum;i++)  //修改其他未连接点的参数
	  {
		  if(adjMat[i][idx]!=0)
		  {
			  if(vertexList[i].wasVisited==false && adjMat[i][idx]>vertexList[i].distance)
			  {
				  vertexList[i].parent=vertexList[idx];
			      vertexList[i].distance=adjMat[i][idx];
			  }
          }
	  }  
  }
  
  public void MSTLength()
  {   int PathLength=0;
	  for(int i=1;i<VertsNum;i++)
	  {
		  PathLength+=vertexList[i].distance;
	  }
	  System.out.println("\n最长生成树路径总长度： "+PathLength);
  }
  
  public static void main(String[] args)
  {  
	 Graph theGraph=new Graph();
     while(true)
     {
    	 theGraph.readGraph();
         theGraph.showAdjMat();
         System.out.print("最大生成树所含路径：");
         theGraph.Prim();
         theGraph.MSTLength();
     }
	 
     
  }
}

class Vertex
{
	public String label; // label (e.g. 'A')
	public boolean wasVisited;
	public int distance;
	public Vertex parent;
	public Vertex() // constructor
	{   
		label=null;
		wasVisited = false;
		distance=0;
		parent=null;
   }
	public Vertex(String lab) // constructor
	{
		label = lab;
		wasVisited = false;
   }
	public String toString()  //rectify the output of Vertex when printed
	{
		return this.label;
	}
} // end class Vertex