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

    







    
	    
    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
亚洲国产精久久久久久久|
一二三四免费观看在线电影|
久久久久久久免费视频|
红杏亚洲影院一区二区三区|
亚洲国产精品无码第一区二区三区|
日韩人妻无码精品久久免费一|
精品国产日韩亚洲一区|
免费高清A级毛片在线播放|
天天摸夜夜摸成人免费视频|
国产亚洲精品bv在线观看|
91免费在线播放|
亚洲午夜电影在线观看高清|
在线观看免费中文视频|
亚洲美女激情视频|
日日麻批免费40分钟日本的|
亚洲国产综合自在线另类|
99久久免费精品国产72精品九九|
亚洲AV综合色区无码二区爱AV|
亚洲精品动漫免费二区|
亚洲日韩精品无码AV海量|
在线A级毛片无码免费真人|
污网站在线观看免费|
亚洲精品无码永久在线观看你懂的|
免费国产成人18在线观看|
亚洲欧洲日韩综合|
国产又粗又猛又爽又黄的免费视频
|
九一在线完整视频免费观看|
a级亚洲片精品久久久久久久|
性色午夜视频免费男人的天堂|
亚洲成av人片不卡无码|
成人免费视频国产|
在线观看特色大片免费网站|
wwwxxx亚洲|
亚洲成a人片在线观看无码|
可以免费看黄的网站|
免费国产草莓视频在线观看黄|
亚洲色婷婷六月亚洲婷婷6月|
永久免费无码日韩视频|
亚洲男女内射在线播放|
成人影片麻豆国产影片免费观看|
九一在线完整视频免费观看|