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

来源:https://www.cnblogs.com/sazxj/archive/2022/11/22/16916851.html
-Advertisement-
Play Games

最小生成樹(貪心演算法) 概念 一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結點,並且有保持圖連通的最少的邊。 連通圖有多種連接方式,而其中最小的連通圖,就是最小生成樹 連通圖分為:無向、有向 無向連通圖:所以頂點相連,但各個邊都沒有方向 有向連通圖:邊有方向 1 ...


最小生成樹(貪心演算法)

概念

  • 一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結點,並且有保持圖連通的最少的邊。
  • 連通圖有多種連接方式,而其中最小的連通圖,就是最小生成樹
  • 連通圖分為:無向、有向
    • 無向連通圖:所以頂點相連,但各個邊都沒有方向
    • 有向連通圖:邊有方向

1.普利姆演算法(Prim)-----最近頂點策略

  • 策略:選擇圖中的一個頂點作為起始點,每一步貪心選擇不在當前生成樹中的最近頂點加入生成樹中,直到所有頂點都加入到樹中。

  • 演算法如下:

    (1)、假如G為無向連通帶權圖,每兩個相鄰節點構成一個帶權邊,其值設為:權值。即:(所有每相鄰的兩個節點都有各自的權值,只是權值大小不同)

    (2)、設集合 W和D,W用於存放G的最小生成樹的頂點集合,D存放G的最小生成樹的權值集合

    (3)、選中G的一個節點 (其索引為data-0) 作為初值,從頂點data0開始構建最小生成樹。集合D的初值為D{}。

    (4)、標記W[data0]=1.表示標記已被選中的節點

    (5)、data0節點找出周圍相鄰,且帶權邊最小的節點(其索引為data-n)。

    (6)、將節點data-n加入集合W。標記W[data-n]=1;將帶權邊(data0,data-n)加入集合D

    (7)、重覆上面步驟

  • 圖解步驟:

    (1)、無向連通圖

(2)、以節點A開始延申:發現(A,G)間的權值最小,於是選中G為連通點

(3)、以A、G節點為頂點找與之相鄰的最小權值邊:發現(G,B)間的帶權邊值最小,選中B

(4)、又以 A、G、B節點為頂點找與之相鄰的最小權值邊:發現(G,E)間的帶權邊值最小,選中E

(5)、又以 A、G、B、E節點為頂點找與之相鄰的最小權值邊:發現(B,A)與(E,F)間的帶權邊值最相同且最小,但A和B節點都是已使用過的節點,所以選中 F 節點

(6)、依次選擇,得到最後的最小生成樹

代碼如下:


import java.util.Arrays;

/*
貪心策略:最小生成樹-普里姆演算法
       :在包含n個頂點的無向連通圖中,找出只有(n-1)條邊且包含n個頂點的連通子圖。使其形成最小連通子圖。連通子圖不能出現迴路
分析:
    1.設置集合 W和集合 D 。其中W存入的是無向連通圖中最小生成樹的頂點集合;D存入的是最小生成樹每相鄰兩個頂點之間的連接邊的集合
    2.另集合W的初值為 W{w0}(即從w0頂點開始構建最小生成樹),另集合D初始值為 D{}
    3.設V為還未被選中的頂點。
    4.從w與v=V-W 中組成的所有帶權邊中選出最小的帶權邊(wn,vn).
    5.將頂點vn加入集合W中。此時集合W{wn,vn},集合D{(wn,vn)}
    6.重覆上面步驟,直到V中所有頂點都加入到了W中,邊有n-1條帶權邊。結束
代碼:探討修路問題
 */
public class test1 {
    public static void main(String[] args) {
        //所有節點
    char[] ndata=new char[]{'A','B','C','D','E','F','G'};
        //獲取節點個數
        int nodes = ndata.length;
        //鄰接矩陣.用較大的數10000表示兩點不連通
        int[][] ndlenght=new int[][]{
                //A   ,B,C,  D  ,  E  ,  F  ,G
                {10000,5,7,10000,10000,10000,2},    //A
                {5,10000,10000,9,10000,10000,3},    //B
                {7,10000,10000,10000,8,10000,10000},//C
                {10000,9,10000,10000,10000,4,10000},//D
                {10000,10000,8,10000,10000,5,4},    //E
                {10000,10000,10000,4,5,10000,6},    //F
                {2,3,10000,10000,4,6,10000},        //G
                                                };
        //創建圖對象
        Chart chart=new Chart(nodes);
        //創建生成數對象
        MinTree mt=new MinTree();
        //創建鄰接矩陣
        mt.creathart(chart,nodes,ndata,ndlenght);
        //獲取矩陣
       // mt.dischart(chart);
        mt.Prim(chart,0);


    }

}

/*
第二步:
創建生成樹對象
 */
class MinTree{
    /**
     * 創建鄰接矩陣
     * @param chart :圖對象
     * @param nodes :節點個數
     * @param ndata :存放節點數據
     * @param ndlenght  :帶權邊
     */
    public void creathart(Chart chart,int nodes,char[] ndata,int[] [] ndlenght){
        //i:已經被選中的節點,ndata[i0]就是為初值,ndata[0]節點開始生成樹。一共有nodes個
        for (int i=0;i<nodes;i++){
            //將當前已被選的節點存入圖對象的ndata中
            chart.ndata[i]=ndata[i];
            //j:還未被選中的節點
            for (int j=0;j<nodes;j++){
                //將所有可能兩兩連接的節點組合,存入圖對象的鄰接矩陣中
                chart.ndlenght[i][j]=ndlenght[i][j];
            }
        }
    }

    //顯示圖矩陣
    public void dischart(Chart chart){
        for (int[] link:chart.ndlenght){
            System.out.println(Arrays.toString(link));
        }
    }


    /**
     * 普里姆演算法:
     *    最小生成樹
     * @param chart:圖
     * @param v :初值
     */
    public void Prim(Chart chart,int v){
        //存放已被選中的節點,初始都為0
        int[] ondata=new int[chart.nodes];
        //標記初值節點已被選中,1(表示被選中了的)
        ondata[v]=1;
        //設即將相連的兩個節點下標為 index1、index2。由於還沒有存入,所以初始為-1
        int index1=-1;
        int index2=-1;
        //由於還不知道第一個邊長為多少,所以先虛擬設置一個最大帶權邊長。後面後被替換的
        int max=10000;
        //k:表示最多生成(n-1)條帶權邊
        for (int k=1;k<chart.nodes;k++){
            //i:表示以被選中的節點;j:還未被選中的節點
            for (int i=0;i<chart.nodes;i++){
                for (int j=0;j<chart.nodes;j++){
                    if (ondata[i]==1&&ondata[j]==0&&chart.ndlenght[i][j]<max){
                        max=chart.ndlenght[i][j];
                        index1=i;
                        index2=j;
                    }
                }
            }
            System.out.println("節點:<"+chart.ndata[index1]+","+chart.ndata[index2]+">,==>帶權邊長:"+max);
            //將當前節點標記為以訪問使用的節點
            ondata[index2]=1;
            //重置max
            max=10000;
        }

    }

}

/*
第一步:
創建圖對象
 */
class Chart{
    int nodes;  //圖中節點個數
    char[] ndata;   //存放節點數據
    int[] [] ndlenght;  //存放帶權邊。也是鄰接矩陣

    //構造器
    public Chart(int nodes) {
        this.nodes = nodes;
        //初始化,數組長度為nodes(節點個數)
        ndata=new char[nodes];
        //初始化,矩陣為nodes行nodes列
        ndlenght=new int[nodes][nodes];
    }
}

結果:

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

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

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

  • 演算法如下:

    (1)、構建有n個頂點的無邊連通圖 W ,

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

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

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

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

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

    • (1)、無邊連通圖 W。與無向連通圖 H1:頂點以排序;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={'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={'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 = 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 +
                '}';
    }
}

結果:


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Android網路請求(2) 在android網路開發中,除get請求外常見的還有post、put、delete這三種,接下來我們將詳細講解這三種請求及參數 GET請求 我們使用過get請求了,對於我們的日常生活中get請求毫無疑問是最常用的請求方式,大部分的瀏覽器搜索都是通過get請求,如在百度上 ...
  • 最近需要接手別人c#那邊組的一個項目新增頁面,但他們的是React的框架,作為一名後端,沒接觸過,一臉懵逼。。。。。。 說哈我的處理思路: 一、先用相應的程式打開該項目的源碼。如:react用vscode打開 二、先找到了頁面,查看頁面結構 這是我後面加的頁面,可以看出來,less類似css樣式 j ...
  • Express 快速創建 Web 伺服器 express 的基本使用 先安裝express包 npm i [email protected] 1.導入 express const express = require('express'); 2.創建 web 伺服器 const app = express( ...
  • 最近用 antd pro 開發了一些 web 小工具。 antd pro 不僅僅是升級版的 antd 組件,更重要的是提供了全套的前端解決方案,包括前端工程的編譯打包,路由配置,數據管理,樣式和資源的引用,和後端的交互方式。 甚至對於網站的國際化也有支持。 本篇是近期使用antd pro 時,用到的 ...
  • 大家好,EluxJS是一套基於“微模塊”和“模型驅動”的跨平臺、跨框架『同構方案』,歡迎瞭解... 可怕的巨石怪 工作中最可怕的是什麼?是遇到業務複雜且亂作一團的巨石應用。改一發而動全身,無法漸進式重構,也沒人敢對歷史包袱進行優化,欠下的代碼債只能像滾雪球一樣越積越多,終於到某天玩不下去,大佬選擇了 ...
  • 傳統大企業更喜歡私有化部署、個性化交付的傳統模式,因為他們需要更強的管控和更高的安全性。 然而,中小企業付費能力有限,需求往往也更加標準化,所以更喜歡價格更低的、訂購更簡單的SaaS產品。 為了滿足不同客戶的需求,多租戶的底層架構設計是至關重要的。 ...
  • 3. Drools入門案例 全套代碼及資料全部完整提供,點此處下載 本小節通過一個Drools入門案例來讓大家初步瞭解Drools的使用方式、對Drools有一個整體概念。 3.1 業務場景說明 業務場景:消費者在圖書商城購買圖書,下單後需要在支付頁面顯示訂單優惠後的價格。具體優惠規則如下: | 規 ...
  • 我們之前有<C++模板編程模塊>中的第<四>節 理解空間配置器allocator優化STL中的Vector 我將在此基礎上加入迭代器功能代碼 Iterator 為什麼可以遍歷所有的容器的方式都一樣? auto it =continer.beign(); for( ;it!=continer.end( ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...