www.pudn.com > MST.rar > Graph.java

//To find a maximum spanning tree of the Graph 
//无向带权图 
// 
//程序名称：寻找一个无向带权图的最大生成树(生成树边的权值和最大) 
//程序用途：算法分析与设计上机实验 
//程序作者：张焕人 
//作者邮箱: renwairen369@yahoo.com.cn  renwairen369@hotmail.com 
//作者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; ydistance)  
		{ 
			idx=i; 
		    distance=vertexList[i].distance;	 
		}   
	  } 
	   
	  vertexList[idx].wasVisited=true; 
	  System.out.print("  "+vertexList[idx].parent.label+"——"+vertexList[idx].label); 
	   
	  for(int i=1;ivertexList[i].distance) 
			  { 
				  vertexList[i].parent=vertexList[idx]; 
			      vertexList[i].distance=adjMat[i][idx]; 
			  } 
          } 
	  }   
  } 
   
  public void MSTLength() 
  {   int PathLength=0; 
	  for(int i=1;i