登入
首頁 所有文章 資料結構 圖形結構-如何求出最小成本擴展樹
長也   2018-12-07 21:26:22(11個月前)    326點閱   0喜歡  0收藏
圖形結構-如何求出最小成本擴展樹  

何謂擴展樹

擴展樹就是以最少的邊,連接圖形中的所有頂點。而在"圖形結構之走訪-DFS與BFS之介紹與範例"一文中所提到的深度優先與廣度優先搜尋也可以求出不同的擴展樹。

最小成本擴展樹

若在邊加上權重,並將權重作為邊的成本或距離,則稱為網路。而一網路之擴展樹具有最小成本,則稱為最小成本擴展樹(minuimum cost spanning tree)。

以下將介紹求得最小成本擴展樹常見的三種演算法,而以下三種算法都屬於一種貪婪算法

(G1)

 

Prim's演算法

此一算法是基於點的延伸,若有一網路G = (V, E),其中集合V = {1, 2, 3......., n},並設定集合U = {1},每次都從集合V當中挑選能與集合U形成最小成本邊的頂點,直到所有的點都被加入到集合U。

以上圖示範此算法的運作過程:

  1. 以頂點1出發,尋找與頂點1可以形成最小成本的邊之頂點6(成本為4):



  2. 尋找能與頂點1、6形成最小成本邊的頂點為5(成本9):



  3. 尋找能與頂點1、6、5形成最小成本邊的頂點2(成本17):



  4. 尋找能與頂點1、2、5、6形成最小成本邊的頂點3(成本6):



  5. 尋找能與頂點1、2、4、5、6形成最小成本邊的頂點4(成本8):



  6. 只剩下頂點7未被加入,加入頂點7(成本12):

Kruskal's 演算法

此一算法基於邊的選擇,每一次都挑選成本最小的邊,若加入此邊不會使擴展樹形成循環,就將邊加入擴展樹,若會形成循環就略過此邊,並且不將此邊加入擴展樹當中。
若以上方的G1為例:

 

  1. 首先找到最小成本的邊1-6(成本4):

  2. 再尋找成本最小的邊2-3(成本6):



  3. 再尋找最小成本的邊2-4(成本8):



  4. 再尋找最小成本的邊5-6(成本9):



  5. 再尋找最小成本的邊3-4(成本11),但若加入會形成循環,故略過。再尋找最小成本的邊2-7(成本12):



  6. 尋找最小成本的邊4-7(成本15),但加入會形成循環,故略過。再尋找最小成本邊1-2(成本17):

關於此算法之證明請參考"Kruskal演算法證明"一文。

程式碼及解說

class Edge{ //紀錄邊
    
    int v1; //點1
    int v2; //點2
    int weight; //邊權重
    boolean edge_del;   //邊是已被刪除(已被選出)
    
}

class Graph{

    int[] v = new int[100];
    int edges;

}

public class Kruskal {
    
    int MAXV = 100; //最大節點數
    
    Graph T = new Graph();  //紀錄Kruskal算法已經加入的節點以及邊個數
    Edge[] E = new Edge[MAXV];  //紀錄相鄰矩陣中所有存在的邊
    int total_e = 0;    //總邊個數
    int total_v = 0;    //總結點個數
    int[][] adjmat = new int[MAXV][MAXV];   //相鄰矩陣
    
    public void build_mat(){    //建立相鄰矩陣
    
        Scanner input = null;
        
        //InputAdjmat.
        try{
        
            input = new Scanner(new FileInputStream("kruskal.txt"));
            
        }catch(Exception e){
        
            System.err.print("File Open Error!");
            System.exit(1);
        
        }
        
        total_v = input.nextInt();
        for(int vi = 1; vi <= total_v; vi++){   //vi及vj從1開始,0不用
        
            for(int vj = 1; vj <= total_v; vj++){
            
                adjmat[vi][vj] = input.nextInt();
                
            }
        
        }
        //close file
        input.close();
    
    }
    
    public void creatEdge(){    //依照相鄰矩陣建立邊
    
        int weight = 0;
        
        for(int i = 1; i <= total_v; i++){
        
            for(int j = i + 1; j <= total_v; j++){
                
                if(adjmat[i][j] != 0){  //如果權重不為0
                    
                    Edge e = new Edge();    //建立一個新的邊
                    e.v1 = i;
                    e.v2 = j;
                    e.weight = adjmat[i][j];
                    e.edge_del = false;

                    E[++total_e] = e;   //將邊加入陣列
                
                }
                
            }
        
        }
    
    }
    
    public void showEdge(){ //印出邊與點的關係
    
        System.out.printf("Total V : %d, Total E = %d \n", total_v, total_e);
        
        for(int i = 1; i <= total_e; i++){
        
            System.out.printf("%s <---> %s  weight = %d \n", E[i].v1, E[i].v2, E[i].weight);
            
        }
        
    }
    
    public Edge findMinedge(){  //尋找最小邊
    
        int min = 0, minweight = 100000;    //初始化邊為極大值
        for(int i = 1; i <= total_e; i++){
        
            if((E[i].edge_del != true) && E[i].weight < minweight){ //循序尋找目前成本最低邊
                
                minweight = E[i].weight;
                min = i;
            
            }
            
        }
        E[min].edge_del = true; //找到之後標記已經輸出並回傳
        return E[min];
    
    }
    
    public boolean cyclic(Edge e){  //檢查是否循環
    
        //先假設無循環,並將該邊加入最小成本擴展圖
        T.v[e.v1]++;    //這裡是紀錄如果加入這個邊,點被加入的次數
        T.v[e.v2]++;
        T.edges++;
        
        //當加入這個邊時,如果兩個點都已經曾經被加入過,代表形成循環
        if(T.v[e.v1] >= 2 && T.v[e.v2] >= 2){
        
            T.v[e.v1]--;
            T.v[e.v2]--;
            T.edges--;
            return true;
            
        }
        else
            return false;
    }
    
    
    public void kruskal(){
    
        int steps = 1;  //次數
        
        //初始化圖形中的節點被加入次數
        for(int i = 0; i <= total_v; i++)
            T.v[i] = 0;
        T.edges = 0;
        
        System.out.println("_________min.Cost Spanning Tree using kruskal_________");
        
        while(T.edges < total_v - 1){   //當加入的邊小於總結點個數減一,則執行
        
            Edge e = findMinedge();
            
            if(cyclic(e) == false){
            
                System.out.printf("Step %d. V%d  <----> V%d  weight = %d \n", steps++, e.v1, e.v2, e.weight);
                
            }
            
        }
        
    }
    
    public static void main(String[] args){
    
        Kruskal k = new Kruskal();
        
        k.build_mat();
        k.creatEdge();
        k.showEdge();
        k.kruskal();
    
    }
    
}

Sollin's 演算法

此算法先列舉所有頂點的最短邊,並刪除重複的,再將其形成的樹林尋找最小邊串聯。

  1. 以G1為例,分別從節點1、2、3、......、7中開始,分別以這些頂點尋找一最短的邊,結果分別為(1, 6)、(2, 3)、(3, 2)、(4, 2)、(5, 6)、(6, 1)、(7, 2)。

  2. 刪去重複的邊,例如(1, 6)與(6, 1)重複,所以只保留(1, 6),刪除重複的邊後只剩下 (1, 6)、(2, 3)、(4, 2)、(5, 6)、(7, 2)五個邊。

  3. 找一成本最小的邊1-2(成本17),將兩棵樹(1, 6, 5和2, 3, 4, 7)連起來,即得到最小成本擴展樹:

到此為止,我們發現無論使用何種方法,都會得到相同的最小成本擴展樹。

結論

  1. 最小成本擴展樹是用最少(小)的邊形成的
  2. Prim's算法以點為主
  3. Kruskal's算法以邊為主
  4. Sollin's算法是列出所有最小成本邊並刪除相同邊,在串聯起來
  5. 無論使用何種算法,皆會得到相同的最小成本擴展樹

 

其實我自己覺得Sollin's的算法蠻雷的......@@,大概是Prim's與Kruskal 的結合體。我最喜歡的是Kruskal的算法,因為我認為以邊為主的思維比較符合最小成本路徑的觀點,之後應該會實作。

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  0則回覆