<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算法】 
	
    

    







    
	    
    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
91视频国产免费|
国产成人亚洲精品蜜芽影院|
亚洲精品国精品久久99热一|
免费v片在线观看无遮挡|
国产成人aaa在线视频免费观看
|
亚洲剧情在线观看|
久久亚洲AV无码精品色午夜|
亚洲欧洲国产精品你懂的|
亚洲a一级免费视频|
亚洲人成依人成综合网|
亚洲好看的理论片电影|
久久久无码精品亚洲日韩按摩|
亚洲国产一区二区三区青草影视
|
日本免费一区二区三区最新vr|
免费理论片51人人看电影|
在线A级毛片无码免费真人|
国产午夜无码视频免费网站|
日批日出水久久亚洲精品tv|
亚洲伦乱亚洲h视频|
亚洲大尺度无码无码专区|
亚洲色四在线视频观看|
亚洲人成人77777在线播放|
99久久国产亚洲综合精品|
精品亚洲国产成人av|
一个人看的免费观看日本视频www
一个人看的免费视频www在线高清动漫
|
国产一区二区三区在线免费观看|
国产福利免费观看|
亚洲人成网站色在线入口
|
永久免费av无码网站韩国毛片|
国产一卡二卡3卡四卡免费|
免费看美女被靠到爽的视频|
亚洲黄片手机免费观看|
国产AV无码专区亚洲A∨毛片|
亚洲一区中文字幕久久|
亚洲最大的成人网|
一二三四在线观看免费中文在线观看|
亚洲第一视频在线观看免费|
鲁大师在线影院免费观看
|
中文字幕无码日韩专区免费|
亚洲精品国产免费|
国产男女性潮高清免费网站|