JAVA—咖啡馆

——欢迎访问rogerfan的博客，常来《JAVA——咖啡馆》坐坐，喝杯浓香的咖啡，彼此探讨一下JAVA技术，交流工作经验，分享JAVA带来的快乐！本网站部分转载文章，如果有版权问题请与我联系。
BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks
【转】图－最小树

图－最小树

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

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

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

不过这里奇怪的是：

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

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

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

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

Graph.mst：返回最小树。

Graph.main：提供简单测试。

代码如下：

 

 1class Stack {
 2    private int[] values;
 3    private int pos = -1;
 4    Stack(int size) {
 5        values = new int[size];
 6    }
 7    void push(int value) { values[++pos] = value; }
 8    int pop() { return values[pos--]; }
 9    int peek() { return values[pos]; }
10    boolean isEmpty() { return pos == -1; }
11}
12
13class Vertex {
14    private Object value;
15    private boolean isVisited;
16    Vertex(Object value) {
17        this.value = value;
18    }
19
20    void visit() { isVisited = true; }
21    void clean() {    isVisited = false; }
22    boolean isVisited() { return isVisited; }
23    Object value() { return value; }
24}
25
26class Graph {
27    private Vertex[] vertexs;
28    private int[][] adjMat;
29    private int pos = -1;
30
31    Graph(int size) {
32        vertexs = new Vertex[size];
33        adjMat = new int[size][size];
34    }
35
36    void add(Object value) {
37        assert pos < vertexs.length;
38        vertexs[++pos] = new Vertex(value);
39    }
40
41    void connect(int from, int to) {
42        adjMat[from][to] = 1;
43        adjMat[to][from] = 1;
44    }
45
46    void connectAll() {
47        for(int i=0; i<= pos; i++)  
48            for(int j=0; j<= pos; j++)
49                adjMat[i][j] = i^j&1;
50        
51    }
52    int findNeighbor(int index) {
53        for(int i=0; i<=pos; i++) {
54            if(adjMat[index][i] == 1 && !vertexs[i].isVisited()) return i;
55        }
56        return -1;
57    }
58
59    Object[] mst(int index) {    //从指定下标的节点开始生成最小数
60        if(vertexs[index] == null) return new Object[0];    //如果图中没有指定下标节点，则退出
61
62        Stack s = new Stack(vertexs.length);    //创建栈记载访问过的节点的下标
63        Object[] result = new Object[pos+1];    //返回的结果
64        int i = 0;    
65        vertexs[index].visit();    //访问0节点
66        result[i++] = vertexs[index].value();
67        s.push(index);    //记录0节点
68
69        while(!s.isEmpty()) {    //如果还有记录的节点则继续
70            index = findNeighbor(s.peek());    //寻找栈顶节点的未访问过的邻居
71            if(index != -1) {    //如果找到
72                vertexs[index].visit();    //访问该节点
73                result[i++] = vertexs[index].value();
74                s.push(index);    //记录该节点
75            } else s.pop();        //没有未访问过的节点，则出栈
76        }    //如果栈未空则代表遍历完成
77        clean();    //清除所有访问标致
78        return result;
79    }
80
81    void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }
82
83    public static void main(String[] args) {
84        Graph g = new Graph(20);
85        g.add('a');
86        g.add('b');
87        g.add('c');
88        g.add('d');
89        g.add('e');
90        g.connectAll();
91        Object[] result = g.mst(0);
92        for(int i=0; i<result.length-1; i++) {
93            System.out.println(result[i] + " --> " + result[i+1]);
94        }
95    }
96}
posted on 2008-05-28 15:58 rogerfan 阅读(710) 评论(0)  编辑  收藏 所属分类: 【JAVA算法】

只有注册用户登录后才能发表评论。
网站导航: