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 閱讀(734) 評論(0)  編輯  收藏  所屬分類: 【JAVA算法】 
	
          

          







          
	    
    




          








          

				

          



    







          
        
	




主站蜘蛛池模板：
望奎县|
象山县|
贵定县|
永川市|
泽州县|
昌图县|
眉山市|
娄底市|
宝坻区|
万载县|
新民市|
石台县|
湖南省|
上林县|
汉源县|
赤水市|
大渡口区|
尼玛县|
冕宁县|
曲松县|
蕲春县|
泗阳县|
仪征市|
卢龙县|
宜州市|
吉安县|
巍山|
永川市|
茂名市|
于都县|
甘泉县|
乌拉特后旗|
梨树县|
宣威市|
司法|
定陶县|
邵阳市|
资源县|
聂拉木县|
南开区|
屏东县|