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

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

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

    
    

    




    







												


        

    
	

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

    







    
	    
    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
无码人妻精品中文字幕免费东京热|
七次郎成人免费线路视频|
日本视频免费高清一本18|
精品亚洲一区二区三区在线播放|
老司机午夜性生免费福利|
成人国产mv免费视频|
亚洲精品宾馆在线精品酒店
|
亚洲国产最大av|
免费毛片a在线观看67194|
亚洲乱码卡三乱码新区|
美女视频黄免费亚洲|
中中文字幕亚洲无线码|
免费看无码自慰一区二区|
亚洲AV成人一区二区三区观看
|
亚洲成a∨人片在无码2023|
免费观看a级毛片|
老湿机一区午夜精品免费福利
|
国产麻豆成人传媒免费观看|
国产精一品亚洲二区在线播放|
人妻在线日韩免费视频|
亚洲精品综合久久中文字幕|
欧洲精品成人免费视频在线观看
|
久久久久亚洲国产AV麻豆
|
国产jizzjizz免费视频|
男女猛烈激情xx00免费视频|
亚洲色欲久久久久综合网|
久久精品免费一区二区三区|
亚洲女人影院想要爱|
国产在线观看免费不卡|
中文无码日韩欧免费视频|
麻豆亚洲av熟女国产一区二|
无人在线观看完整免费版视频|
国产亚洲精品AAAA片APP|
国产成A人亚洲精V品无码性色|
美女视频黄是免费的网址|
黄色一级视频免费|
亚洲日本一区二区三区|
成人免费视频网址|
亚欧国产一级在线免费|
亚洲欧洲精品国产区|
亚洲第一区精品观看|