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

    







    
	    
    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
久久久久成人精品免费播放动漫|
中文字幕不卡高清免费|
我的小后妈韩剧在线看免费高清版|
国产亚洲精品无码成人|
成在线人视频免费视频
|
亚洲欧洲无码一区二区三区|
国产成人yy免费视频|
亚洲最大的视频网站|
日韩毛片免费无码无毒视频观看
|
老司机午夜免费视频|
亚洲AV中文无码乱人伦在线视色|
看亚洲a级一级毛片|
亚洲av麻豆aⅴ无码电影|
jizz中国免费|
亚洲AV无码乱码在线观看裸奔|
美女被cao网站免费看在线看|
亚洲av无码乱码国产精品fc2|
96免费精品视频在线观看|
亚洲一级高清在线中文字幕|
中文字幕无码不卡免费视频|
亚洲精品美女久久7777777|
免费h黄肉动漫在线观看|
久久国产精品免费一区|
亚洲国产一区二区a毛片|
免费A级毛片无码无遮挡内射|
亚洲国产成人久久精品大牛影视|
亚洲精品无码日韩国产不卡?V|
a毛片免费全部播放完整成|
亚洲国产国产综合一区首页|
一二三四在线播放免费观看中文版视频
|
国产jizzjizz免费看jizz|
免费人成又黄又爽的视频在线电影|
国产亚洲日韩一区二区三区|
91精品免费不卡在线观看|
亚洲日韩AV一区二区三区中文|
www.91亚洲|
最近免费中文字幕高清大全
|
香蕉视频在线观看亚洲|
性盈盈影院免费视频观看在线一区|
免费人成网站永久|
亚洲福利视频一区二区三区|