<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        

    
	

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

    

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

管理

			
			
				

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

    

			    		
		
    
	
    

    


    



    
	
					

    
	
	
	
    
		
    圖－最小樹
    

    

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

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

    關于深度優(yōu)先遍歷請參見深度優(yōu)先遍歷。
    

    不過這里奇怪的是：
    

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

    然后每兩個點之間的線段就是最小樹的結果，即a --> b, b --> c,  c --> d, d --> e
    

    似乎不用圖這樣復雜的結構支撐。
    

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

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

    







    
	    
    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
成人免费视频网站www|
久久精品国产亚洲av天美18|
中国一级全黄的免费观看|
亚洲AⅤ永久无码精品AA|
亚洲精品色在线网站|
最近的中文字幕大全免费版|
亚洲三级在线视频|
青青草免费在线视频|
亚洲日韩AV一区二区三区四区
|
丰满亚洲大尺度无码无码专线|
成人a免费α片在线视频网站|
亚洲欧美中文日韩视频|
国产国产人免费人成免费视频|
亚洲乱码无人区卡1卡2卡3|
四虎永久免费地址在线观看|
免费一级做a爰片久久毛片潮|
亚洲日本在线观看视频|
a毛片免费全部在线播放**|
亚洲欧洲国产日韩精品|
99爱在线精品免费观看|
亚洲AV无码专区国产乱码不卡|
亚洲 综合 国产 欧洲 丝袜|
a毛片全部播放免费视频完整18|
99久久亚洲综合精品成人网|
欧洲乱码伦视频免费|
在线观看亚洲专区|
亚洲精品白浆高清久久久久久|
最近在线2018视频免费观看|
亚洲最大成人网色香蕉|
又爽又黄无遮挡高清免费视频|
a级毛片视频免费观看|
亚洲丰满熟女一区二区v|
免费在线不卡视频|
国产一级淫片a免费播放口|
亚洲ts人妖网站|
亚洲国产精品自在拍在线播放|
久久青草免费91线频观看不卡|
亚洲综合激情五月色一区|
久久久久无码专区亚洲av
|
MM1313亚洲精品无码久久|
亚洲熟妇中文字幕五十中出|