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

1.大理论的一些资料

 

带权图

带权是说的是在图的连接边是有长度。我们来模拟这个环境：

 

中国的20个城市，每个城市好比一个图的顶点，火车在地面上开，有火车的轨道将20个城市连接在一起了

而火车的轨道好比是边，而轨道连接各个城市之间的的有长度的，那么这就形成了一个图----有火车的轨道网络，

这个例子说的就是带权的图了。

 

当把权值当做边的特性的时候，一些有趣的并且复杂的问题就出现了，

什么是带权的最小生成树？

什么是两个顶点间的最短距离？

这两个问题都在现实的生活中有非常大的意义的

 

2.小理论的一些资料（重要概念）

 

 

带权图的最小生成树

 

    我们先来看普通的最小生成树。在有向图中创建一个树比在无向图中要复杂哦。当所有的边拥有相同的权值，问题就变的简单了，

    算法可以任意选择一条边加入最小生成树。但是当边具有不同的权值时，需要用一些算法策略来选择正确的边。

 

    一个实例：丛林中的有线电视

     假设要再一个虚拟的国家M的6个城市之间架设有线电视网络，把它们都连接起来。五条边可以连接6个点，但是要怎么连接五条边呢

     才能让线路最短。

 

     步骤1.

    随便 找一个顶点A，作为办公地点

 

      步骤2.

   找出各个直接与A连接的点，并且比较出最小的那条边。连接这条边的点就作为第二办公地点B，并且将这边架设好

 

    步骤3.

        规则1 已经架设好的边不修改

        规则2 新建的办公地点开始办公，步骤类似于步骤2，并且将步骤2中遗留下来的边的长度一起比较，选择出最短的那条作为下一个办公点

 

 

 

   步骤4 

       直到没有边或者全部连接好了顶点了，那么就停止了 ，连接线就是最短的线了。（其实表示还是不详细哦）

 

  三类顶点

  1.已经有办事处并且用电缆连接的城市，他们是最小生成树的顶点

  2.还没有连接，也没有办事处的城市，但是知道了他们连接到至少有一个已经有办事处的城市电缆的安装造价了。

      这些城市就叫做边缘城市

  3还不知道任何信息的城市的     

 

  随着算法的进行，城市虫第三类到第二类到第一类

 

 

    设计算法：

 

    优先级队列

    正如前面例子描述的那样，执行算法的关键行为是保存两个城市建立连接的造价单。通过选择造价最低的项，就可以决定下一条建在何处

     建议用优先级队列来实现这个用于反复选择最小造价价值的表，而不用链表或者数组。这是解决最小生成树的有效方式。在正式的程序中，

     优先级队列可能基于堆来实现。这加快了加大的优先级队列的操作，然而，在实例中，将用数组实现的队列进行优先级队列。

 

      算法要点

      下面用图的术语，重申下算法：

      从一个顶点开始，把它放入树的集合中，然后重复做下面的事情：

      1.找到最新的顶点到其他顶点的所以边，这些顶点不能在树的集合中，把这些边放入优先级队列中

      2.找出权值最小的边，把它和塔所到达的顶点放入树 的结合中。

      重复这些步骤，直到所以项目的顶点都在树的集合中了。这是工作就结束了。

 

      在步骤1,最新的意味着最近放入树中的。此步骤的边可以在邻接矩阵中找到，步骤1完成后，表中包含了所有的边，这些边都是从树中顶点

      到它们的不在树中的邻接点的连接

 

 

  无用边

 

  在表剩余条目中，想要把某些连接删除比较困难，它们都是从当前城市到已经拥有办事处的城市的连接，但是如果不做这个工作，就可能会导致

  安装不必要的优先电缆

    在程序的算法中，也要确保优先级队列中不能有连接已在书中的顶点的边，每次向树中增加顶点后，都要遍历优先级队列查找并删除这样的边，

    这样做以后，要使优先队列中任意时刻只保存一条树中顶点到某边缘点的边就变得容易了，也就是说，优先级队列中应该包含一条到达

    某个第二类顶点的边      

 

  部分代码

  package endual;

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 < nVerts-1) { //顶点的数大于树的数
			
			vertexList[currentVert].isInTree = true ; //已经放入到树中了
			nTree++ ; //树中的数目加一个
			
			//insert edges adjacent to currentVert into Pq
			
			for (int j=0; j<nVerts; j++) {
				if (j == currentVert) {
					continue ;
				}
				if (vertexList[j].isInTree) {
					continue; 
				}
				
				int distance = adjMat[currentVert][j] ;
				if (distance == INFINITY) { //skip if no edg 如果没有边，那么就跳过
					continue ;
					
				}
				
				putInPQ(j,distance) ; //放入到优先队列中去
				
			} //end for
			
			if (thePQ.size()==0) {
				System.out.println("GPAPH NOT CONNECTED") ;
				return ;
			}
			
			//remove edge with mini distance , from PQ
			
			Edge the Edge = thePQ.removeMin() ; //将最小的边移除掉
			int sourceVert = theEdge.srcVert ;
			correntVert = theEdge.destVert ;
			
			//displayedge for source to current 
			
			System.out.println(vertexList[sourceVert].label) ;
			System.out.println(VertextList[currentVert].label) ;
			System.out.println(" ") ;
			
		} // end while
		
		// mst is complete
		for (int j=0; j<nVerts; j++) {
			verttexlist[j].inInTree = false ; //没有被放入到最小生成树中
		}
		
		
	}
	
}

 

 

 

 

全部代码

首先我们创建边了

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.size; j++) {

 

if (item.distance > 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<size-1; j++) {

this.queArray[j] = this.queArray[j+1] ;

}

this.size-- ;

}

public Edge peekMin() { //只是查看并没有删除

//this.size = 

return this.queArray[this.size - 1];

}

public Edge peelN(int n) { //n从0开始的

return this.queArray[n] ;

}

//当前的数目

public int size() { //当前的数目呢

return this.size ;

}

//是否为空

public boolean isEmply() {

if (this.size != 0) {

return false ;

}

return true ;

}

//是否为满

public boolean isFull(){

if (this.size == this.SIZE) {

return true ;

}

return false ;

}

//找到一个序号

public int find(int findDex) { //找到特殊的边

for (int j=0; j < this.size; j++) {

if (this.queArray[j].destVert == findDex) {

return j ;

}

}

return -1 ;

}

} // end class

 

 

 

 

 

 

然后我们创建图了，在图中创建方法

 

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 < this.MAX_SIZE; i++) {

for (int j = 0; j < this.MAX_SIZE; j++) {

 

this.adjMat[i][j] = INFINITY; // 顶点之间是无线的长的

 

}

}

 

}

 

// 向图中插入顶点

public void insertVertex(char a) {

 

Vertex v = new Vertex(a);

this.vertexList[this.nVerts] = v;

this.nVerts++;

 

}

 

// 插入带全的边

public void addEdge(int start, int end, int weight) {

 

this.adjMat[start][end] = weight;

this.adjMat[end][start] = weight;

 

}

 

// 显示顶点

public void displayVertex(int v) {

 

System.out.println(vertexList[v].getLabel());

 

}

 

// 带权图的最小生成树方法

public void mstw() {

 

this.currentVert = 0;// 从第一个顶点开始取，就是在数组中保存的第一个顶点开始的

 

while (this.nTree < this.nVerts - 1) {

 

this.vertexList[this.currentVert].setInTree(true); // 当前节点放入到tree中，其实这个是数组形状的最小生成树

this.nTree++; // 那么当前的树要增加一个了

 

// 将和当前顶点连接的顶点的边长放入到优先队列中去

for (int i = 0; i < this.nVerts; i++) {

 

if (i == this.currentVert) { // 当前节点是自身本身的话，那么就跳出，寻找下一个

continue;

}

 

if (this.vertexList[i].isInTree() == true) { // 当前节点以及在树中了，也跳出循环寻找下一个

continue;

}

 

int dis = this.adjMat[this.currentVert][i];

if (dis == this.INFINITY) { // 当前节点与节点i直接的距离是无线大，所以没有连接的

 

continue;

}

// 那么当前节点与连接的顶点就是dis了

putInPQ(i, dis); //多次循环，将优先队列中是否有相同长度的老边给代替掉

 

} //end for

if (thePQ.size() == 0) { //如果队列中的长度是0那么就说没有点了

System.out.println("graph not connected") ; //该图是一个没有边连接的图

}

//现在就显示

//优先队列中移除最小的树的边，来生成我们要用的最小的生成树

Edge minEdge = thePQ.removeMin() ;

int sourceVert = minEdge.srcVert ;//开始的点

this.currentVert = minEdge.destVert ; //当前节点

System.out.println(this.vertexList[sourceVert].getLabel()) ;

System.out.println(this.vertexList[currentVert].getLabel()) ;

System.out.println(" ") ;

} // 当图中的顶点都没有的时候就跳出循环

//复原我们的初始顶点

initialGraph() ;

 

}

 

private void initialGraph() {

for(int j=0; j < this.nVerts; j++) {

this.vertexList[j].setInTree(false) ;

}

}

 

private void putInPQ(int i, int dis) {

//is there another edge with the same destination vertex ?

//是否存在另一条边的长度和新的边的长度是一样的顶点

int queueIndex = thePQ.find(dis) ; //寻找到一个距离

if (queueIndex != -1) { //如果那么是不等于，没有的话是返回-1

Edge tempEdge = thePQ.peelN(queueIndex) ; //找到这个边

int oldDist = tempEdge.distance ; //边的长度是多少，该边的长度   

if (oldDist > 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) ; //插入到新的队列中

}

}

 

}

 

}