图－最小树
如果一个图中所有点都是联通的，求最小树可以将图遍历完成，这里的最小是指边最少，跟边长没有关系。算法利用深度优先遍历，记载每个遍历过的节点，将节点按照遍历顺序记录下来就是所谓的最小树。
关于深度优先遍历请参见深度优先遍历。
不过这里奇怪的是：
假如所有节点之间是双向联通的，只用生成一个数组，装入所有的节点，例如{'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;}void push(int value) { values[++pos] = value; }int pop() { return values; }int peek() { return values; }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;adjMat = new int;}void add(Object value) {assert pos < vertexs.length;vertexs[++pos] = new Vertex(value);}void connect(int from, int to) {adjMat = 1;adjMat = 1;}void connectAll() {for(int i=0; i<= pos; i++)for(int j=0; j<= pos; j++)adjMat = i^j&1;}int findNeighbor(int index) {for(int i=0; i<=pos; i++) {if(adjMat == 1 && !vertexs.isVisited()) return i;}return -1;}Object[] mst(int index) {//从指定下标的节点开始生成最小数if(vertexs == null) return new Object;//如果图中没有指定下标节点，则退出Stack s = new Stack(vertexs.length);//创建栈记载访问过的节点的下标Object[] result = new Object;//返回的结果int i = 0;vertexs.visit();//访问0节点result = vertexs.value();s.push(index);//记录0节点while(!s.isEmpty()) {//如果还有记录的节点则继续index = findNeighbor(s.peek());//寻找栈顶节点的未访问过的邻居if(index != -1) {//如果找到vertexs.visit();//访问该节点result = vertexs.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 + " --> " + result);}}}
页:
[1]