最小生成樹之普利姆演算法與克魯斯卡爾演算法（貪心演算法）

結果：

2.,克魯斯卡爾演算法(Kruskal)----最短邊策略

• 策略：每一次貪心的選擇從剩下的邊中最小的邊且不產生環路的，加入到已選邊的集合中，直到所有頂點都加入進來，

• 按照權值從小到大選擇n-1條邊，并且這些邊不構成環路，

• 演算法如下：

  （1）、構建有n個頂點的無邊連通圖 W ，

  （2）、對無向連通圖 H 中的各個帶權邊從小到大排序

  （3）、依次從小到大將 H 中的帶權邊加入到 W中（期間不能構成環路）

• 演算法圖解及判斷環路：

  • 環路：已加入加入到無邊聯通圖中的頂點的終點不能相同

  • 終點：將所有頂點從小到大排序后，某個頂點的終點就是"與它相連的最大的頂點";

  • （1）、無邊連通圖 W，與無向連通圖 H（1:頂點以排序;2.權值以排序）

    • 頂點的終點：此時由于還沒有加入，所以W中所有的各個頂點的終點是自己本身

  ?

• （2）、將H中從小到大排序后的邊依次加入 W中，

  • （2.1）、第一次：<A,C>=4，

  • 頂點的終點：因為頂點是已排序為{A,B,C,D},而目前加入到W中的只有{A，C}，所以A與C連通的最大頂點是：A--->C;C--->C

- （2.2）、第二次：<B,D>=5，

- 頂點的終點：此時**W**中有{A，C}，{B，D}，由于目前{B，D}還沒有與{A，C}連通，所以B與D連通的最大頂點是：B--->D;D--->D,

- （2.3）、第三次：<C,D>=6，這里雖然前面C與D被加入過，但它們的終點卻不同，

- 頂點的終點：此時**W**中有{A，C}，{B，D}，{C，D}，由于{C，D}的加入導致{A,B,C,D}相互連接，所最大頂點是：A--->D;B--->D;C--->D;D--->D,

- （2.4）、第四次：<A,D>=7，由于前面得出A，與D的最大頂點(終點)相同為D，如果加入會構成環路，所以不能加入.跳過此邊，加入下一條邊

- （2.5）、第五次：<A,B>=8，由于前面得出A，與B的最大頂點(終點)相同為D，如果加入會構成環路，所以不能加入，所以加入下一條邊，發現沒有，所有邊都已加入到了，

• （3）、注意：在（2.3）時，其實所有頂點都已加入到了W中，所以就不需要判斷后面的了，后面的結論只是為了說明終點與環路，

• 代碼如下：

import java.util.Arrays;

/**
 * 最小生成樹：克魯斯卡爾演算法
 * 將無向連通圖中的各個邊從小到大排序，依次放入無邊連通圖中（不能出現環路）
 */
public class test1 {

    private int geshu;  //邊的個數
    private char[] data; //存放節點
    private int[][] allquanzhi;   //存放帶權邊，鄰接矩陣
    //標記不能相連通的兩個節點，即不相鄰的兩個節點所形成的帶權邊，為Integer最大值
    private static final int maxlen = Integer.MAX_VALUE;

    public static void main(String[] args) {
      //  char[] data=https://www.cnblogs.com/sazxj/p/{'A','B','C','D','E'};
//        int[][] allquanzhi={
//                {0,20,maxlen,60,15},
//                {20,0,42,maxlen,maxlen},
//                {maxlen,42,0,30,maxlen},
//                {60,maxlen,30,0,23},
//                {15,maxlen,maxlen,23,0},
//                };
        char[] data=https://www.cnblogs.com/sazxj/p/{'A','B','C','D'};
        int[][] allquanzhi={
                {0,8,4,7},
                {8,0,maxlen,5},
                {4,maxlen,0,6},
                {7,5,6,0}
                    };
        test1 t=new test1(data,allquanzhi);
        //列印矩陣
        t.dayinjuzheng();
        Bian[] bians=t.andbian();
        System.out.println("排序前的邊集合"+Arrays.toString(bians));
        t.biansort(bians);
        System.out.println("排序后的邊集合"+Arrays.toString(bians));
        t.KrusKal();

    }

    //定義構造器
    public test1(char[] data, int[][] allquanzhi) {
        //初始化頂點數
        int spotgeshu = data.length;
        //初始化頂點（節點）
        this.data = https://www.cnblogs.com/sazxj/p/data;
        //初始化 邊
        this.allquanzhi = allquanzhi;
        //統計邊的個數
        for (int i = 0; i < spotgeshu; i++) {
            for (int j = i+1; j < spotgeshu; j++) {
                if (this.allquanzhi[i][j] < maxlen) {
                    geshu++;
                }
            }
        }
    }

    //列印鄰接矩陣
    public void dayinjuzheng() {
        System.out.println(geshu);
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data.length; j++) {
                //格式化輸出
                System.out.printf("%15d\t", +allquanzhi[i][j]);
            }
            System.out.println();
        }
    }


    /*
    對邊排序：冒泡《從小到大》
     */
    public void biansort(Bian[] bian){
        for (int i=bian.length-1;i>0;i--){
            for (int j=0;j<i;j++){
                if (bian[j].bianquanzhi>bian[j+1].bianquanzhi){
                    Bian temp=bian[j];
                    bian[j]=bian[j+1];
                    bian[j+1]=temp;
                }
            }
        }
    }

    /*
    判斷頂點是否存在
    回傳頂點的索引
     */
public  int ismbian(char ch){
    for (int i=0;i<data.length;i++){
        if (data[i]==ch){
            return i;
        }
    }
    //如果ch不是頂點就回傳-1
    return -1;
}

/*
將所以相鄰邊存入Bian[]中
 */
public Bian[] andbian(){
    int index=0;
    Bian[] bians=new Bian[geshu];
    for (int i=0;i<data.length;i++){
        for (int j=i+1;j<data.length;j++){
            if (allquanzhi[i][j]!=maxlen){
                bians[index++]=new Bian(data[i],data[j],allquanzhi[i][j]);
            }
        }
    }
    return bians;
}


/*
獲取小標為i的頂點的終點，用于判斷兩個頂點的終點是否相同
star:存入的是頂點的終點的索引，初始化為{0，0，0，0，...},
i:頂點的索引
 */
public int getEnd(int[] star,int i){
    //動態的判斷以此頂點的索引，
    //相連的前一個頂點的終點索引就是后一個頂點的索引
    //由于第一次的頂點的終點是自己的索引都
    //如果在star中找到了終點
    while (star[i]!=0){
        //就將此終點的值變為新的頂點的索引（找到此索引對應的頂點的終點，直到新的索引在star中沒有找到終點，即為0，就將此索引回傳為最初始的節點的終點索引）
        i=star[i];
    }
    //回傳為終點
    return  i;
}


/*
最小生成樹克魯斯卡爾演算法
 */
public  void KrusKal(){
    int index=0;    //最后結果陣列的索引
    //存放最小生成樹每個頂點的終點
    int[] star=new  int[geshu];
    //保存最終生成樹
    Bian[] fin=new  Bian[geshu];
    //獲取邊的集合
    Bian[] andnewbian = andbian();
    //對所有邊進行排序
    biansort(andnewbian);
    //遍歷邊集合，在判斷的同時判斷是否形成回路
    for (int i=0;i<geshu;i++){
        //上面andbian存放獲得的邊的類：bians[index++]=new Bian(data[i],data[j],allquanzhi[i][j]);
        //獲取第一邊的起點（頂點）,對應的是data[i]
        int h1=ismbian(andnewbian[i].da1);
        //獲取第一條邊的第二個頂點,對應的是data[j]
        int h2=ismbian(andnewbian[i].da2);
        //獲取第一個頂點的終點
        int end = getEnd(star, h1);
        //獲取第二個頂點的終點
        int end1 = getEnd(star, h2);
        //判斷回路:如果沒有構成回路
        if (end!=end1){
            //設定end1為已有生成數的終點
            star[end]=end1;
            //此時最終生成樹有了一條邊
            fin[index++]=andnewbian[i];
        }
    }
    System.out.println("最后生成樹："+Arrays.toString(fin));
    System.out.println("最小生成樹:");
    for (int i=0;i<index;i++){
        System.out.println(fin[i]);
    }
}

}


/*
邊類
 */
class Bian{
    //組成一條邊的兩個節點
    char da1;
    char da2;
    //邊權值
    int bianquanzhi;

    public Bian(char da1, char da2, int bianquanzhi) {
        this.da1 = da1;
        this.da2 = da2;
        this.bianquanzhi = bianquanzhi;
    }

    @Override
    public String toString() {
        return "bian{" +
                "da1=" + da1 +
                ", da2=" + da2 +
                ", bianquanzhi=" + bianquanzhi +
                '}';
    }
}

結果：

標籤：Java

上一篇：富文本中提取文本的方法分享

下一篇：第2-4-2章 規則引擎Drools入門案例-業務規則管理系統-組件化-中臺