图－代权最小树

图中代权的最小树的问题如下:

如果N个城市之间（图中的顶点）要修公路（图中的边）以使所有的城市联通，求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示，公路可以图中的边表示，公路的长度用边长表示，公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度，这与以前的不代权的最小树生成算法有很大的区别。

算法描述如下：

    任选一个节点开始，将该节点标志为已访问过的节点。也就是最小树中的节点。并设置为当前节点。
    1 寻找此访问节点的所有的邻接顶点，将边置入优先队列。邻接顶点不考虑已标志为访问的节点，因为它已在结果中。
    2 重复 步骤1 直到没有新的边被发现。此时在所有发现的边中找到最小的边，将其终点顶点标志为已访问，放入最小树中。并设置为当前节点
    3 重复 步骤 1，2，直到边的队列中没有多余的边，算法结束。

    注意：这里的优先级队列是个修正过的优先级队列，每次向该队列中加入一条新边时后，会检查是否有与新边终点相同的第二条边的存在，如果有，则删除边长较大的边。因为如果存在这样的边说明，有两条从已访问过节点到相同目标节点的路径存在，如果这样的话只用保留最小的那条边即可。

这里的图采用Graph 图－邻接矩阵法 表示。

算法实际上是作如下操作：

    先准备好一个优先级队列，里面以边长为关键值存放边，边的起点表示已被访问过的节点，而边的终点表示未访问的节点。将某节点标志为访问过节点。开始算法。
    寻找该访问过节点的所有边，并记录边长，放入边优先级队列中;
    找到所有从已访问过的节点到未访问节点的边中的最小边;
    将最小边连接的顶点设置为访问过,重复以上过程，直到所有节点都变成已访问。

主要的类如下：

    Edge：记载边

    PriorityQ：修正后的优先级队列

    Vertex：顶点

    Gragh：图

        Gragh.mstw()：最小树生成算法

        Gragh.main()：提供简单测试

代码如下:

class Edge {	//边：记载起始，与终止节点的下标，以及边的长度
	private int from;
	private int to;
	private int length;
	Edge(int from, int to, int length) {
		this.from = from;
		this.to = to;
		this.length = length;
	}

	int from() { return from; }	//起点
	int to() { return to; }	//终点
	int length() { return length; }	//边长
}

/**
 * 修正过的优先级队列，边长最小的队列的头部，且队列中不会出现到达同一个节点
 * 的两条边，如果添加新边到队列中时出现这种情况，则队列自动删除边长较大的边。
 */
class PriorityQ {	
	private Edge[] edges;
	private int pos = -1;
	PriorityQ(int size) {	//创建指定长度的优先级队列
		edges = new Edge[size];
	}

	void add(Edge edge) {	//添加新边到队列中
		assert pos < edges.length;
		//按照边长将新边插入队列中合适的位置
		int index = ++pos;
		while(index > 0 && edges[index-1].length() < edge.length()) {
			edges[index] = edges[index-1];
			index--;	
		}
		edges[index] = edge;	

		//在队列中检查是否有与新边终点相同的边，如果有则作修正处理
		removeDuplicate(edge.to());		
	}

	private void removeDuplicate(int to) {	//根据终点在队列中查找重复的边，并处理
		int count = 0;	//记录找到同样终点的边的个数
		for(int index=pos; index>-1; index--) {
			if(edges[index].to() == to) count++;	
			if(count == 2) {	//将第二次找到的边作删除处理
				for(int i=index; i<pos; i++) edges[i] = edges[i+1];
				pos--;
				return;
			}
		}
	}

	Edge remove() {	//移出并返回最小的边
		return edges[pos--];	
	}

	boolean isEmpty() { return pos == -1; }
}

class Vertex {	//顶点类，记载顶点的value，并可以记录是否访问过
	private Object value;
	private boolean isVisited;
	Vertex(Object value) {
		this.value = value;
	}

	void visit() { isVisited = true; }
	void clean() {	isVisited = false; }
	boolean isVisited() { return isVisited; }
	Object value() { return value; }
	@Override public String toString() { return "" + value; }
}

class Graph {	//无向图，记录顶点，顶点之间的边，以及边的长度
	private Vertex[] vertexs;
	private int[][] adjMat;
	private int length = 0;
	private static final int INFINITY = -1;	//表示不存在边时的状态

	Graph(int size) {	//初始化图的数据结构，包括顶点，边，边都置为不存在
		vertexs = new Vertex[size];	
		adjMat = new int[size][size];
		for(int i=0; i<size; i++) 
			for(int j=0; j<size; j++)
				adjMat[i][j] = INFINITY;
	}

	void add(Object value) {	//添加新的顶点
		assert length <= vertexs.length;
		vertexs[length++] = new Vertex(value);
	}

	void connect(int from, int to, int length) {	//顶点之间添加边，指定边长
		adjMat[from][to] = length;
		adjMat[to][from] = length;
	}

	/**
	 * 在邻接矩阵中，查找指定顶点的未访问过邻居顶点
	 * 如果从从起点到终点的边存在，且没有标志为访问，则返回终点下标。
	 * @param offset 指定开始查找的列
	 * @param index	指定查找的行
	 */
	int findNeighbor(int index,int offset) {	//
		for(int i=offset; i<length; i++) {
			if(adjMat[index][i] != INFINITY && !vertexs[i].isVisited()) return i;
		}
		return -1;
	}

	Edge[] mstw(int index) {	//最小树生成算法，index为开始的坐标
		assert vertexs[index] != null;
		Edge[] result = new Edge[length-1]; //生成结果数组，边的数量为顶点数量-1
		PriorityQ q = new PriorityQ(length);	//准备优先级队列
		int pos = -1;
		vertexs[index].visit();	//将起始顶点标志为访问过的
		while(true) {
			//寻找已访问过的节点与未访问过节点之间的边，并加入优先级队列
			int i = -1;
			while((i = findNeighbor(index,i+1)) != -1) {	
				Edge e = new Edge(index,i,adjMat[index][i]);
				q.add(e);	
			}
			if(q.isEmpty()) break;	//如果队列中没有多余的边，算法结束
			
			//在队列中找到边长最短的边，将终点节点标志为访问过，并将此边从队列中删除
			result[++pos] = q.remove();	
			index = result[pos].to();	//以新的终点作为起点，准备下一次迭代
			vertexs[index].visit();
		}
		clean();	//将所有访问标志复位
		return result;
	}

	void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }

	Object get(int index) { return vertexs[index]; }

	public static void main(String[] args) {	//测试
		Graph g = new Graph(20);
		//添加顶点
		g.add('a');
		g.add('b');
		g.add('c');
		g.add('d');
		g.add('e');
		g.add('f');
		//连接顶点，并指明边长
		g.connect(0,1,6);
		g.connect(0,3,4);
		g.connect(1,2,10);
		g.connect(1,3,7);
		g.connect(1,4,7);
		g.connect(2,3,8);
		g.connect(2,4,5);
		g.connect(2,5,6);
		g.connect(3,4,12);
		g.connect(4,5,7);
		int sum = 0;	//记录总边长
		for(Edge e: g.mstw(4)) {	//以任意顶点开始生成最小树
			System.out.println(g.get(e.from()) + " -- " + g.get(e.to()) + " : " + e.length());
			sum += e.length();
		}
		System.out.println(sum);
	}
}

 

 

评论

3 楼 abo 2008-05-28  

如果所有的边的端点必须是顶点（城市），这样的公路网络只会在偶然的情况下是总长度最小的。

2 楼 woailuo 2008-05-28  

正好在复习,看看!

1 楼 yxgd 2008-05-27  

喜欢!辛苦了.