JAVA—咖啡館
          
				
          ——?dú)g迎訪問rogerfan的博客，常來《JAVA——咖啡館》坐坐，喝杯濃香的咖啡，彼此探討一下JAVA技術(shù)，交流工作經(jīng)驗(yàn)，分享JAVA帶來的快樂！本網(wǎng)站部分轉(zhuǎn)載文章，如果有版權(quán)問題請(qǐng)與我聯(lián)系。
          
			          		
		
          
	
          

          

          
	
          
		
          
		    
		        
		        BlogJava
首頁
新隨筆
聯(lián)系
聚合

管理

			
			
				

          
	
          
		
          
			
			
			
				 
				447 
				Posts ::
				145 Stories
				::
				368 Comments
				::
				0 Trackbacks
			
		
          
	
          

          

			          		
		
          
	
          

          


          



          
	
					

          
	
	
	
          
		
          圖－最小樹
          

          

          如果一個(gè)圖中所有點(diǎn)都是聯(lián)通的，求最小樹可以將圖遍歷完成，這里的最小是指邊最少，跟邊長沒有關(guān)系。
          

          算法利用深度優(yōu)先遍歷，記載每個(gè)遍歷過的節(jié)點(diǎn)，將節(jié)點(diǎn)按照遍歷順序記錄下來就是所謂的最小樹。
          

          關(guān)于深度優(yōu)先遍歷請(qǐng)參見深度優(yōu)先遍歷。
          

          不過這里奇怪的是：
          

          假如所有節(jié)點(diǎn)之間是雙向聯(lián)通的，只用生成一個(gè)數(shù)組，裝入所有的節(jié)點(diǎn)，例如{'a','b','c','d','d'}
          

          然后每兩個(gè)點(diǎn)之間的線段就是最小樹的結(jié)果，即a --> b, b --> c,  c --> d, d --> e
          

          似乎不用圖這樣復(fù)雜的結(jié)構(gòu)支撐。
          

          不過這里還是給出了按照?qǐng)D來產(chǎn)生最小樹的辦法。
          

          Graph.mst：返回最小樹。
          

          Graph.main：提供簡單測(cè)試。
          

          代碼如下：
          

          

           
          

           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) {    //從指定下標(biāo)的節(jié)點(diǎn)開始生成最小數(shù)
          
          60        if(vertexs[index] == null) return new Object[0];    //如果圖中沒有指定下標(biāo)節(jié)點(diǎn)，則退出
          
          61
          
          62        Stack s = new Stack(vertexs.length);    //創(chuàng)建棧記載訪問過的節(jié)點(diǎn)的下標(biāo)
          
          63        Object[] result = new Object[pos+1];    //返回的結(jié)果
          
          64        int i = 0;    
          
          65        vertexs[index].visit();    //訪問0節(jié)點(diǎn)
          
          66        result[i++] = vertexs[index].value();
          
          67        s.push(index);    //記錄0節(jié)點(diǎn)
          
          68
          
          69        while(!s.isEmpty()) {    //如果還有記錄的節(jié)點(diǎn)則繼續(xù)
          
          70            index = findNeighbor(s.peek());    //尋找棧頂節(jié)點(diǎn)的未訪問過的鄰居
          
          71            if(index != -1) {    //如果找到
          
          72                vertexs[index].visit();    //訪問該節(jié)點(diǎn)
          
          73                result[i++] = vertexs[index].value();
          
          74                s.push(index);    //記錄該節(jié)點(diǎn)
          
          75            }           else s.pop();        //沒有未訪問過的節(jié)點(diǎn)，則出棧
          
          76        }              //如果棧未空則代表遍歷完成
          
          77        clean();    //清除所有訪問標(biāo)致
          
          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 閱讀(730) 評(píng)論(0)  編輯  收藏  所屬分類: 【JAVA算法】 
	
          

          







          
	    
    




          








          

				

          



    







          
        
	




主站蜘蛛池模板：
正蓝旗|
辽源市|
措勤县|
华容县|
黎平县|
高唐县|
琼中|
莱西市|
尖扎县|
陵川县|
新民市|
资阳市|
平昌县|
获嘉县|
台山市|
锦屏县|
余江县|
巴林右旗|
托里县|
巴中市|
安达市|
丘北县|
武宁县|
科技|
大姚县|
厦门市|
通渭县|
阿尔山市|
阿拉尔市|
南昌县|
大方县|
新沂市|
武隆县|
萝北县|
齐河县|
大足县|
尼玛县|
黔西县|
广元市|
松滋市|
繁昌县|