带权图的最小生成树 （代码自己写）

public class ValueGraph {
  
	/**
	 * 有权图的最小生成树的方法mstw()
	 */

	public void mstw() {
		
		currentVert = 0 ; //选择从开始点出发
		/**
		 * 算法中while中执行，循环结束条件是所以顶点都在书中了，循环中完成下面的操作
		 * 1.当前的顶点放入到树中去，从第一个开始
		 * 2.连接这个顶点的边全部放入到优先级队列中（如果合适）
		 * 3.从优先级队列中删除权值最小的边。这条边的目的顶点变成当前顶点
		 * 
		 * 在看看这些步骤的细节、
		 * 在步骤1中，通过标记currentVert所指顶点的isInTree字段来表示该顶点放入树中
		 * 在步骤2中，连接这个顶点的边插入优先级队列。通过在连接矩阵中扫描号是currentVert的
		 * 行寻找需要的边。只要下面任意的一个条件为真，那么这条边就不能放入到队列中
		 * 
		 * 1.源点和终点是相同的
		 * 2.原点在树中了（重点看下这个概念）
		 * 3.源点和终点之间没有边（链接矩阵中对于的值等于无限大）
		 * 
		 * 如果没有一个条件为真，调用putInPQ()方法把这条边放入到这个优先队列中。实际上，正如下面要到的，这个列程并不总是把
		 * 边放入到优先队列中去的
		 * 
		 * 在步骤三种，将最小权值的边从优先级队列中删掉，把这条边和该边的终点加入树，并显示原点和终点
		 * 
		 * 最后的for循环将数据复原
		 * 
		 * 
		 * 
		 */
		while (nTree 

package endual;

public class Edge {

	public int srcVert ; //一个顶点开始的序列好
	public int destVert ; //一个顶点结束的序号
	public int distance ;//从开始到介绍的长度
	
	public Edge(int srcVert, int destVert, int distance) {
		super();
		this.srcVert = srcVert;
		this.destVert = destVert;
		this.distance = distance;
	}
	
	
	
}

package endual;

public class Vertex {

	private char label; // 顶点的标记
	private boolean isInTree; // 是否在最小生成树中了
	private boolean isVisited; // 是否已经被访问

	public Vertex(char label) {
		super();
		this.label = label;
		this.isInTree = false;
		this.isVisited = false;

	}

	public char getLabel() {
		return label;
	}

	public void setLabel(char label) {
		this.label = label;
	}

	public boolean isInTree() {
		return isInTree;
	}

	public void setInTree(boolean isInTree) {
		this.isInTree = isInTree;
	}

	public boolean isVisited() {
		return isVisited;
	}

	public void setVisited(boolean isVisited) {
		this.isVisited = isVisited;
	}

}

package endual;
 
public class PriorityQ {
 
 private final int SIZE = 20;
 private Edge[] queArray;
 private int size;
 
 public PriorityQ() {
 super();
 this.queArray = new Edge[this.SIZE];
 this.size = 0; // 当前队列中的数目
 }
 
 // 插入边长
 public void insert(Edge item) {
 
 int j;
 for (j = 0; j  this.queArray[j].distance) {
 break;
 } // 如果当前插入的边长当前的节点长度大，那么就停止掉，寻找到数组中的位子
 
 // 因为现在数组的位子是有人的，那么就以为，把这个位子空出来
 for (int k = this.size - 1; k >= j; k--) {
 this.queArray[k + 1] = this.queArray[k];
 }
 // 空出来的位子就插入进去
 this.queArray[j] = item;
 size++; // 当前队列中的数要增加一个
 
 }
 
 } // end
 
 // 移除最小的那个边
 
 public Edge removeMin() {
 
 this.size = this.size - 1;
 return this.queArray[this.size];
 }
 
 
 public void removeN(int n) { //移除在数组中为是n的数据
 
 for (int j=n; j

package endual;
 
public class Graph {
 
 private final int MAX_SIZE = 20;
 private Vertex[] vertexList;
 private final int INFINITY = 10000000; // 认为是这个无限大的，测试两个点之间的距离是不是之间相连的
 
 private int adjMat[][]; // 存放在顶点是不是连接点，也就是也矩阵的方式进行存放
 private int nVerts; // 当前图中的数量
 
 private int currentVert;
 private PriorityQ thePQ;
 private int nTree; // 当前树的长度
 
 public Graph() {
 super();
 this.vertexList = new Vertex[this.MAX_SIZE];
 this.adjMat = new int[19][19];
 this.initialAdjMat();
 this.nVerts = 0;
 this.currentVert = 0;
 this.thePQ = new PriorityQ();
 this.nTree = 0;
 }
 
 private void initialAdjMat() {
 
 for (int i = 0; i  dis) {
 //如果老边的长度是大于新边的长度的话
 thePQ.removeN(queueIndex) ; //移除这个老的节点
 Edge theEdge = new Edge(this.currentVert,i, dis) ;//创建一个新的边
 thePQ.insert(theEdge) ; //插入到新的队列中
 }
 
 else {//如果没有这样的边
 
 Edge theEdge = new Edge(this.currentVert,i, dis) ;//创建一个新的边
 thePQ.insert(theEdge) ; //插入到新的队列中
 }
 
 }
 
 }
 
}