图－最小树

如果一个图中所有点都是联通的，求最小树可以将图遍历完成，这里的最小是指边最少，跟边长没有关系。

算法利用深度优先遍历，记载每个遍历过的节点，将节点按照遍历顺序记录下来就是所谓的最小树。

关于深度优先遍历请参见深度优先遍历。

不过这里奇怪的是：

假如所有节点之间是双向联通的，只用生成一个数组，装入所有的节点，例如{'a','b','c','d','d'}

然后每两个点之间的线段就是最小树的结果，即a --> b, b --> c,  c --> d, d --> e

似乎不用图这样复杂的结构支撑。

不过这里还是给出了按照图来产生最小树的办法。

Graph.mst：返回最小树。

Graph.main：提供简单测试。

代码如下：

class Stack {
	private int[] values;
	private int pos = -1;
	Stack(int size) {
		values = new int[size];
	}
	void push(int value) { values[++pos] = value; }
	int pop() { return values[pos--]; }
	int peek() { return values[pos]; }
	boolean isEmpty() { return pos == -1; }
}

class Vertex {
	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; }
}

class Graph {
	private Vertex[] vertexs;
	private int[][] adjMat;
	private int pos = -1;

	Graph(int size) {
		vertexs = new Vertex[size];
		adjMat = new int[size][size];
	}

	void add(Object value) {
		assert pos < vertexs.length;
		vertexs[++pos] = new Vertex(value);
	}

	void connect(int from, int to) {
		adjMat[from][to] = 1;
		adjMat[to][from] = 1;
	}

	void connectAll() {
		for(int i=0; i<= pos; i++)  
			for(int j=0; j<= pos; j++)
				adjMat[i][j] = i^j&1;
		
	}
	int findNeighbor(int index) {
		for(int i=0; i<=pos; i++) {
			if(adjMat[index][i] == 1 && !vertexs[i].isVisited()) return i;
		}
		return -1;
	}

	Object[] mst(int index) {	//从指定下标的节点开始生成最小数
		if(vertexs[index] == null) return new Object[0];	//如果图中没有指定下标节点，则退出

		Stack s = new Stack(vertexs.length);	//创建栈记载访问过的节点的下标
		Object[] result = new Object[pos+1];	//返回的结果
		int i = 0;	
		vertexs[index].visit();	//访问0节点
		result[i++] = vertexs[index].value();
		s.push(index);	//记录0节点

		while(!s.isEmpty()) {	//如果还有记录的节点则继续
			index = findNeighbor(s.peek());	//寻找栈顶节点的未访问过的邻居
			if(index != -1) {	//如果找到
				vertexs[index].visit();	//访问该节点
				result[i++] = vertexs[index].value();
				s.push(index);	//记录该节点
			} else s.pop();		//没有未访问过的节点，则出栈
		}	//如果栈未空则代表遍历完成
		clean();	//清除所有访问标致
		return result;
	}

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

	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.connectAll();
		Object[] result = g.mst(0);
		for(int i=0; i<result.length-1; i++) {
			System.out.println(result[i] + " --> " + result[i+1]);
		}
	}
}

 

评论

2 楼 boy in the road 2008-05-22  

最近开始看《数据结构与算法——java语言》，特来讨教的

1 楼 longshou 2008-05-21  

[color=red][/color][size=medium][/size]Peter怎么不写点感情日志阿，好让我来踩踩阿，不过程序写的很漂亮